30 citations · 157 across the 83 of their papers we have counts for
6 papers · 2 filters
Planar Disjoint-Paths Completion
Isolde Adler, Stavros G. Kolliopoulos, Dimitrios M. Thilikos
introduce {\sc Planar Disjoint Paths Completion}, a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follo…
An -approximation for covering and packing minor models of
Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau +1
Given two graphs and , we define (resp. ) as the minimum number of vertices (resp. edges) whose removal from produces…
Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism
Eunjung Kim, Christophe Paul, Ignasi Sau +1
In this paper we design {\sf FPT}-algorithms for two parameterized problems. The first is \textsc{List Digraph Homomorphism}: given two digraphs and and a list of allowed v…
An FPT 2-Approximation for Tree-Cut Decomposition
Eunjung Kim, Sang-il Oum, Christophe Paul +2
The tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110:47-66, 2015] with the help of tree-cut decompositions. In certain cases, tree-cut…
Variants of Plane Diameter Completion
Petr A. Golovach, Clément Requilé, Dimitrios M. Thilikos
The {\sc Plane Diameter Completion} problem asks, given a plane graph and a positive integer , if it is a spanning subgraph of a plane graph that has diameter at most $d…
Editing to a Planar Graph of Given Degrees
Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof +2
We consider the following graph modification problem. Let the input consist of a graph , a weight function , a cost function $c\colo…