Steiner trees for hereditary graph classes: a treewidth perspective
From MaRDI portal
Publication:2663041
DOI10.1016/j.tcs.2021.03.012zbMath1477.68203arXiv2004.07492OpenAlexW3134208201MaRDI QIDQ2663041
Nick Brettell, Matthew Johnson, Erik Jan van Leeuwen, Daniël Paulusma, Giacomo Paesani, Hans L. Bodlaender
Publication date: 15 April 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.07492
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boolean-width of graphs
- Clique-width of graphs defined by one-vertex extensions
- Graph minors. V. Excluding a planar graph
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- The Steiner problem with edge lengths 1 and 2
- Complement reducible graphs
- Improved Steiner tree algorithms for bounded treewidth
- Steiner trees for hereditary graph classes
- The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Approximating clique-width and branch-width
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Steiner trees, connected domination and strongly chordal graphs
- On the delta-wye reduction for planar graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Reducibility among Combinatorial Problems
- Colouring H-free graphs of bounded diameter.
- Clique-width for hereditary graph classes
- Improved Bounds for the Flat Wall Theorem
- Bounding the Mim-Width of Hereditary Graph Classes.
This page was built for publication: Steiner trees for hereditary graph classes: a treewidth perspective
