Improved Steiner tree algorithms for bounded treewidth

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

zbMATH Keywords

exact algorithm; bounded treewidth; fixed parameter tractable; \(k\)-cardinality tree; (prize-collecting) Steiner tree

Mathematics Subject Classification ID

05C05: Trees

05C85: Graph algorithms (graph-theoretic aspects)

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