Faster algorithm for optimum Steiner trees

DOI10.1016/J.IPL.2011.08.005zbMATH Open1260.68305OpenAlexW2078404396MaRDI QIDQ1944205FDOQ1944205

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

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

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)

Cites Work

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

Cited In (17)

• 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
• Title not available (Why is that?)
• 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
• 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)