A Faster Algorithm for the Steiner Tree Problem

DOI10.1007/11672142_46zbMath1136.68468OpenAlexW1579272824MaRDI QIDQ5449830

Stefan Richter, Daniel Mölle, Peter Rossmanith

Publication date: 19 March 2008

Published in: STACS 2006 (Search for Journal in Brave)

Full work available at URL: http://publications.rwth-aachen.de/record/47972

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Reoptimization of Steiner trees: changing the terminal set ⋮ Computing optimal Steiner trees in polynomial space ⋮ A factoring approach for the Steiner tree problem in undirected networks ⋮ Exponential approximation schemata for some network design problems ⋮ Splitting trees at vertices ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Enumerate and expand: Improved algorithms for connected vertex cover and tree cover ⋮ A Lagrangean-based decomposition approach for the link constrained Steiner tree problem ⋮ Definition and algorithms for reliable Steiner tree problem ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Algorithmic aspects of Steiner convexity and enumeration of Steiner trees ⋮ On the Hardness of Reoptimization ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems