Improved Steiner tree algorithms for bounded treewidth
From MaRDI portal
Publication:1932355
DOI10.1016/j.jda.2012.04.016zbMath1257.05166WikidataQ56977061 ScholiaQ56977061MaRDI QIDQ1932355
Markus Chimani, Bernd Zey, Petra Mutzel
Publication date: 18 January 2013
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2012.04.016
exact algorithm; bounded treewidth; fixed parameter tractable; \(k\)-cardinality tree; (prize-collecting) Steiner tree
Related Items
Strong Steiner Tree Approximations in Practice, Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics, On Hop-Constrained Steiner Trees in Tree-Like Metrics, Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, P versus NPC: minimum Steiner trees in convex split graphs, Computing directed Steiner path covers, Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions, Steiner trees for hereditary graph classes: a treewidth perspective, Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The Steiner forest problem revisited
- The Steiner problem with edge lengths 1 and 2
- Polynomially solvable special cases of the Steiner problem in planar networks
- Treewidth. Computations and approximations
- Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth
- An O ( n log n ) approximation scheme for Steiner tree in planar graphs
- Steiner trees, partial 2–trees, and minimum IFI networks
- Fourier meets M\"{o}bius: fast subset convolution
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Send-and-Split Method for Minimum-Concave-Cost Network Flows
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Linear-time computation of optimal subgraphs of decomposable graphs
- Practical Partitioning-Based Methods for the Steiner Problem
- Treewidth: Structure and Algorithms
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- The steiner problem in graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth