A primal-dual approximation algorithm for the Steiner forest problem

DOI10.1016/0020-0190(94)00034-4zbMath0807.68058OpenAlexW2109719517MaRDI QIDQ1327312

R. Ravi

Publication date: 15 June 1994

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

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00034-4

zbMATH Keywords

undirected graphprimal-dual approximation algorithmminimum \(q\)-Steiner forest problem

Mathematics Subject Classification ID

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

Related Items

Improved algorithms for joint optimization of facility locations and network connections, Distributed multicast routing in point-to-point networks, On the approximability of dense Steiner problems, A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A fast algorithm for Steiner trees
• Some generalizations of the steiner problem in graphs
• Une heuristique pour le problème de l'arbre de Steiner
• Probabilistic analysis of an lp relaxation bound for the steiner problem in networks
• The computation of nearly minimal Steiner trees in graphs
• Steiner's problem in graphs and its implications
• The steiner problem in graphs
• A faster approximation algorithm for the Steiner problem in graphs
• Steiner tree problems