Faster algorithm for optimum Steiner trees

DOI10.1016/J.IPL.2011.08.005MaRDI QIDQ1944205zbMATH OpenOpenAlexFDO

Authors 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 programminggraph algorithmsSteiner tree problemdesign of algorithmstree composition

Mathematics Subject Classification ID

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

Recommendations

• A faster approximation algorithm for the Steiner problem in graphs
• A Faster Algorithm for the Steiner Tree Problem
• A faster approximation algorithm for the Steiner problem in graphs
• scientific article; zbMATH DE number 4063109
• A faster approximation algorithm for the Steiner tree problem in graphs

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3384060 (Why is no real title available?)
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Dynamic programming for minimum Steiner trees
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Faster Steiner Tree Computation in Polynomial-Space
• Fibonacci heaps and their uses in improved network optimization algorithms
• Fourier meets M\"{o}bius: fast subset convolution
• Send-and-Split Method for Minimum-Concave-Cost Network Flows
• The Steiner problem with edge lengths 1 and 2
• The steiner problem in graphs

Cited in

(17)

• Steiner trees with bounded RC-delay
• A Faster Algorithm for the Steiner Tree Problem
• Faster exact algorithms for steiner trees in planar networks
• Implications, conflicts, and reductions for Steiner trees
• Implications, conflicts, and reductions for Steiner trees
• Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees
• Faster algorithms for Steiner tree and related problems: from theory to practice
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• Dynamic programming for minimum Steiner trees
• scientific article; zbMATH DE number 169458 (Why is no real title available?)
• Solving Steiner trees: Recent advances, challenges, and perspectives
• The rainbow Steiner tree problem
• A faster approximation algorithm for the Steiner problem in graphs
• Strong Steiner tree approximations in practice
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• Improved Steiner tree algorithms for bounded treewidth
• Steiner trees with bounded RC-delay

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1944205)