A faster approximation algorithm for the Steiner tree problem in graphs

DOI10.1016/0020-0190(93)90201-JMaRDI QIDQ1802062zbMATH OpenOpenAlexFDO

Authors Alex Zelikovsky

Publication date 8 August 1993

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

Full work available at URL https://doi.org/10.1016/0020-0190(93)90201-j

zbMATH Keywords

approximation algorithmscombinatorial problemsSteiner tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A faster approximation algorithm for the Steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs
• scientific article; zbMATH DE number 4063109
• scientific article; zbMATH DE number 1445376
• scientific article; zbMATH DE number 4049088

Cites work

• scientific article; zbMATH DE number 3677874 (Why is no real title available?)
• scientific article; zbMATH DE number 26676 (Why is no real title available?)
• scientific article; zbMATH DE number 125502 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 742979 (Why is no real title available?)
• A faster approximation algorithm for the Steiner problem in graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• Fibonacci heaps and their uses in improved network optimization algorithms

Cited in

(20)

• A faster approximation algorithm for the Steiner problem in graphs
• A fast algorithm for computing steiner edge connectivity
• The influence of preprocessing on Steiner tree approximations
• Faster algorithm for optimum Steiner trees
• An improved approximation scheme for the Group Steiner Problem
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• scientific article; zbMATH DE number 4063109 (Why is no real title available?)
• scientific article; zbMATH DE number 169458 (Why is no real title available?)
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• Digital data networks design using genetic algorithms
• On efficient implementation of an approximation algorithm for the Steiner tree problem
• Steiner trees and polyhedra
• A note on A faster approximation algorithm for the Steiner problem in graphs
• Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
• scientific article; zbMATH DE number 5313630 (Why is no real title available?)
• The Power of Dynamic Distance Oracles
• Approximating the tree and tour covers of a graph
• The Clustered Selected-Internal Steiner Tree Problem
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Strong Steiner tree approximations in practice

This page was built for publication: A faster approximation algorithm for the Steiner tree problem in graphs

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