Browsing Department of Informatics by Author "van Leeuwen, Erik Jan"
Now showing items 1-3 of 3
-
Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
Lima, Paloma T.; van Leeuwen, Erik Jan; van der Wegen, Marieke (Journal article; Peer reviewed, 2020)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 vertex path between every pair of its ... -
Parameterized complexity of the spanning tree congestion problem
Bodlaender, Hans L.; Fomin, Fedor; Golovach, Petr; Otachi, Yota; van Leeuwen, Erik Jan (Peer reviewed; Journal article, 2012-09)We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class ... -
Subexponential-time parameterized algorithm for Steiner tree on planar graphs
Pilipczuk, Marcin; Pilipczuk, Michal Pawel; van Leeuwen, Erik Jan; Sankowski, Piotr (Peer reviewed; Journal article, 2013)The well-known bidimensionality theory provides a method for designing fast, subexponential-time parameterized algorithms for a vast number of NP-hard problems on sparse graph classes such as planar graphs, bounded genus ...