A series of approximation algorithms for the acyclic directed Steiner tree problem
From MaRDI portal
Publication:679453
DOI10.1007/BF02523690zbMath0873.68079MaRDI QIDQ679453
Publication date: 28 May 1997
Published in: Algorithmica (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
68W10: Parallel algorithms in computer science
Related Items
Unnamed Item, New primal-dual algorithms for Steiner tree problems, Inapproximability of survivable networks, Combinatorial optimization in system configuration design, Worst-case performance of Wong's Steiner tree heuristic, The polymatroid Steiner problems, A greedy approximation algorithm for the group Steiner problem, Unnamed Item, A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Worst-case performance of Rayward-Smith's Steiner tree heuristic
- The Steiner problem with edge lengths 1 and 2
- The rectilinear Steiner arborescence problem
- The Steiner tree problem
- An 11/6-approximation algorithm for the network Steiner problem
- The computation of nearly minimal Steiner trees in graphs
- Cost-minimal trees in directed acyclic graphs
- On the hardness of approximating minimization problems
- A faster approximation algorithm for the Steiner problem in graphs