1 citations · 2 across the 9 of their papers we have counts for
9 papers · 1 filter
Romeo and Juliet Meeting in Forest Like Regions
Neeldhara Misra, Manas Mulpuri, Prafullkumar Tale +1
The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of agents.…
Parameterized Complexity of Weighted Multicut in Trees
Esther Galby, Dániel Marx, Philipp Schepper +2
The Edge Multicut problem is a classical cut problem where given an undirected graph , a set of pairs of vertices , and a budget , the goal is to determine if th…
Reducing the Vertex Cover Number via Edge Contractions
Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau +2
The CONTRACTION(vc) problem takes as input a graph on vertices and two integers and , and asks whether one can contract at most edges to reduce the size of a min…
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
Dániel Marx, Pranabendu Misra, Daniel Neuen +1
Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. The goal of this pa…
-approximate Reductions: a Novel Source of Heuristics for Better Approximation Algorithms
Fredrik Manne, Geevarghese Philip, Saket Saurabh +1
Lokshtanov et al.~[STOC 2017] introduced \emph{lossy kernelization} as a mathematical framework for quantifying the effectiveness of preprocessing algorithms in preserving approxim…
On the Parameterized Complexity of \textsc{Maximum Degree Contraction} Problem
Saket Saurabh, Prafullkumar Tale
In the \textsc{Maximum Degree Contraction} problem, input is a graph on vertices, and integers , and the objective is to check whether can be transformed into a g…