Improved Steiner tree algorithms for bounded treewidth

DOI10.1016/j.jda.2012.04.016zbMath1257.05166OpenAlexW2003272551WikidataQ56977061 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 algorithmbounded treewidthfixed parameter tractable\(k\)-cardinality tree(prize-collecting) Steiner tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Computing directed Steiner path covers ⋮ Steiner trees for hereditary graph classes: a treewidth perspective ⋮ Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ P versus NPC: minimum Steiner trees in convex split graphs ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth ⋮ Strong Steiner Tree Approximations in Practice ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics

Cites Work

• Unnamed Item
• 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
• 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

This page was built for publication: Improved Steiner tree algorithms for bounded treewidth