Dynamic programming for minimum Steiner trees
From MaRDI portal
Publication:2464320
DOI10.1007/s00224-007-1324-4zbMath1148.68038OpenAlexW2003753063MaRDI QIDQ2464320
Bernhard Fuchs, Xinhui Wang, Peter Rossmanith, Stefan Richter, Walter Kern, Daniel Mölle
Publication date: 19 December 2007
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: http://e-archive.informatik.uni-koeln.de/492/2/zaik2005-492.pdf
Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Approximation algorithms (68W25)
Related Items (23)
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ On Directed Steiner Trees with Multiple Roots ⋮ Computing optimal Steiner trees in polynomial space ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Probability Steiner trees and maximum parsimony in phylogenetic analysis ⋮ Optimization of urban transport; an alternative to checkerboard towns plans ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Faster algorithm for optimum Steiner trees ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes ⋮ The number of tree stars is \(O^{*}(1.357^k)\) ⋮ Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Approaches to the Steiner Problem in Networks ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
This page was built for publication: Dynamic programming for minimum Steiner trees