5 papers
Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
Sándor Kisfaludi-Bak, Dániel Marx
We give approximation schemes for Subset TSP and Steiner Tree on unit disk graphs, and more generally, on intersection graphs of similarly sized connected fat (not necessarily conv…
The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
Jakob Greilhuber, Dániel Marx
For fixed sets of non-negative integers, the -domination framework introduced by Telle [Nord. J. Comput. 1994] captures many classical graph problems. For a grap…
On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
Sujoy Bhore, Baris Can Esmer, Daniel Marx +1
We study the Steiner Tree problem on the intersection graph of most natural families of geometric objects, e.g., disks, squares, polygons, etc. Given a set of objects in the pl…
Generalized Graph Packing Problems Parameterized by Treewidth
BarıŠCan Esmer, Dániel Marx
-Packing is the problem of finding a maximum number of vertex-disjoint copies of in a given graph . -Partition is the special case of finding a set of vertex-disjoint…
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
Jacob Focke, Florian Hörsch, Shaohua Li +1
The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph and demand graph on a set of terminals, the task…