Faster algorithm for optimum Steiner trees

DOI10.1016/J.IPL.2011.08.005zbMath1260.68305OpenAlexW2078404396MaRDI QIDQ1944205

Jens Vygen

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.08.005

zbMATH Keywords

dynamic programmingSteiner tree problemdesign of algorithmsgraph algorithmstree composition

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (9)

Steiner Trees with Bounded RC-Delay ⋮ The rainbow Steiner tree problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ Strong Steiner Tree Approximations in Practice ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Steiner trees with bounded RC-delay ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Implications, conflicts, and reductions for Steiner trees

Cites Work

• Unnamed Item
• Unnamed Item
• The Steiner problem with edge lengths 1 and 2
• Dynamic programming for minimum Steiner trees
• Faster Steiner Tree Computation in Polynomial-Space
• Fourier meets M\"{o}bius: fast subset convolution
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Fibonacci heaps and their uses in improved network optimization algorithms
• The steiner problem in graphs

This page was built for publication: Faster algorithm for optimum Steiner trees