14 citations · 21 across the 10 of their papers we have counts for
16 papers
Steiner Forest for -Subgraph-Free Graphs
Tala Eagling-Vose, David C. Kutner, Felicia Lucke +4
Our main result is a full classification, for every connected graph , of the computational complexity of Steiner Forest on -subgraph-free graphs. To obtain this dichotomy, we…
Separator Theorem and Algorithms for Planar Hyperbolic Graphs
Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen +2
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incompa…
Computing Subset Vertex Covers in -Free Graphs
Nick Brettell, Jelle J. Oostveen, Sukanya Pandey +3
We consider a natural generalization of Vertex Cover: the Subset Vertex Cover problem, which is to decide for a graph , a subset and integer , if has…
The Parameterized Complexity of the Survivable Network Design Problem
Andreas Emil Feldmann, Anish Mukherjee, Erik Jan van Leeuwen
For the well-known Survivable Network Design Problem (SNDP) we are given an undirected graph with edge costs, a set of terminal vertices, and an integer demand fo…
Induced Disjoint Paths in AT-free Graphs
Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen
Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices (except perhaps their end-ve…
Upper Bounding Rainbow Connection Number by Forest Number
L. Sunil Chandran, Davis Issac, Juho Lauri +1
A path in an edge-colored graph is rainbow if no two edges of it are colored the same, and the graph is rainbow-connected if there is a rainbow path between each pair of its vertic…
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
Hans Bodlaender, Nick Brettell, Matthew Johnson +3
We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced…
Algorithms for the rainbow vertex coloring problem on graph classes
Paloma T. Lima, Erik Jan van Leeuwen, Marieke van der Wegen
Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow…
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
Iyad Kanj, Christian Komusiewicz, Manuel Sorge +1
A fundamental graph problem is to recognize whether the vertex set of a graph can be bipartitioned into sets and such that and satisfy properties an…
Subexponential-time Algorithms for Maximum Independent Set in -free and Broom-free Graphs
Gábor Bacsó, Daniel Lokshtanov, Dániel Marx +3
In algorithmic graph theory, a classic open question is to determine the complexity of the Maximum Independent Set problem on -free graphs, that is, on graphs not containing a…
Disconnected Cuts in Claw-free Graphs
Barnaby Martin, Daniel Paulusma, Erik Jan van Leeuwen
A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The decision problem whether a graph has a disconnected cut is called Disc…
Polynomial kernelization for removing induced claws and diamonds
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk +2
A graph is called (claw,diamond)-free if it contains neither a claw (a ) nor a diamond (a with an edge removed) as an induced subgraph. Equivalently, (claw,diamond)-…
Reducing a Target Interval to a Few Exact Queries
Jesper Nederlof, Erik Jan van Leeuwen, Ruben van der Zwaan
Many combinatorial problems involving weights can be formulated as a so-called ranged problem. That is, their input consists of a universe , a (succinctly-represented) set famil…
Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs
Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen
The Induced Graph Matching problem asks to find k disjoint induced subgraphs isomorphic to a given graph H in a given graph G such that there are no edges between vertices of diffe…
k-Gap Interval Graphs
Fedor V. Fomin, Serge Gaspers, Petr Golovach +5
We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real…
Parameterized Complexity of Firefighting Revisited
Marek Cygan, Fedor V. Fomin, Erik Jan van Leeuwen
The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a fire…