Recent results on approximating the Steiner tree problem and its generalizations

DOI10.1016/S0304-3975(99)00192-9zbMath0953.68120MaRDI QIDQ1566960

Vijay V. Vazirani

Publication date: 5 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Steiner tree problem

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

Related Items

Competitive and deterministic embeddings of virtual networks, A partition-based relaxation for Steiner trees, A note on Steiner tree games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast algorithm for Steiner trees
• The ellipsoid method and its consequences in combinatorial optimization
• A primal-dual approximation algorithm for generalized Steiner network problems
• An 11/6-approximation algorithm for the network Steiner problem
• Random pseudo-polynomial algorithms for exact matroid problems
• Vertex packings: Structural properties and algorithms
• Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
• Improved Approximations for the Steiner Tree Problem
• Multiway cuts in node weighted graphs
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• RNC-approximation algorithms for the steiner problem
• Optimum branchings