Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions

DOI10.1007/s00453-014-9934-0zbMath1312.68230arXiv1305.7448OpenAlexW2067500596WikidataQ59567461 ScholiaQ59567461MaRDI QIDQ2343089

Stefan Fafianie, Jesper Nederlof, Hans L. Bodlaender

Publication date: 4 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.7448

zbMATH Keywords

dynamic programmingtreewidthSteiner treeexact algorithmsalgorithm engineeringexperimental evaluation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation

Uses Software

• SteinLib
• GeoSteiner
• Treewidthlib
• ComputeTW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient sets in partial \(k\)-trees
• Treewidth computations. I: Upper bounds
• A parameterized view on matroid optimization problems
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• The Steiner tree problem
• Treewidth. Computations and approximations
• Improved Steiner tree algorithms for bounded treewidth
• Speeding Up Dynamic Programming with Representative Sets
• Tour Merging via Branch-Decomposition
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Steiner trees, partial 2–trees, and minimum IFI networks
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Steiner problem in networks: A survey
• An integer linear programming approach to the steiner problem in graphs
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Reducibility among Combinatorial Problems
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• On Steiner’s Problem with Rectilinear Distance
• An algorithm for the steiner problem in graphs

This page was built for publication: Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions