14 citations · 19 across the 2 of their papers we have counts for
9 papers
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…