Recent results on approximating the Steiner tree problem and its generalizations
From MaRDI portal
Publication:1566960
DOI10.1016/S0304-3975(99)00192-9zbMath0953.68120MaRDI QIDQ1566960
Publication date: 5 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
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