Browsing Bergen Open Research Archive by Author "Knop, Dusan"
Now showing items 1-4 of 4
-
Complexity of the Steiner Network Problem with Respect to the Number of Terminals
Eiben, Eduard; Knop, Dusan; Panolan, Fahad; Suchý, Ondřej (Journal article; Peer reviewed, 2019)In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T subseteq V(G) with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H ... -
Kernelization of Graph Hamiltonicity: Proper H-Graphs
Chaplick, Steven; Fomin, Fedor; Golovach, Petr; Knop, Dusan; Zeman, Peter (Journal article; Peer reviewed, 2021)We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization ... -
Recognizing Proper Tree-Graphs
Chaplick, Steven; Golovach, Petr; Hartmann, Tim; Knop, Dusan (Journal article; Peer reviewed, 2020)We investigate the parameterized complexity of the recognition problem for the proper H-graphs. The H-graphs are the intersection graphs of connected subgraphs of a subdivision of a multigraph H, and the properness means ... -
Treewidth is NP-Complete on Cubic Graphs
Bodlaender, Hans L.; Bonnet, Édouard; Jaffke, Lars; Knop, Dusan; Lima, Paloma Thome de; Milanič, Martin; Ordyniak, Sebastian; Pandey, Sukanya; Suchy, Ondrey (Journal article; Peer reviewed, 2023)In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new ...