30 citations · 157 across the 83 of their papers we have counts for
8 papers · 1 filter
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…
Minors in graphs of large -girth
Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau +1
For every , let denote the graph with two vertices and parallel edges. The -girth of a graph is the minimum number of edges of a subgraph of $G…
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…