A series of approximation algorithms for the acyclic directed Steiner tree problem

DOI10.1007/BF02523690zbMath0873.68079OpenAlexW2005771129MaRDI QIDQ679453

Alexander Z. Zelikovsky

Publication date: 28 May 1997

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02523690

zbMATH Keywords

acyclic directed Steiner tree problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items

Bounded Degree Group Steiner Tree Problems ⋮ $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ On approximating degree-bounded network design problems ⋮ Directed Steiner trees with diffusion costs ⋮ A practical greedy approximation for the directed Steiner tree problem ⋮ New primal-dual algorithms for Steiner tree problems ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ Online Buy-at-Bulk Network Design ⋮ An improved approximation scheme for the Group Steiner Problem ⋮ A Practical Greedy Approximation for the Directed Steiner Tree Problem ⋮ Navigational guidance -- a deep learning approach ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Combination algorithms for Steiner tree variants ⋮ Register loading via linear programming ⋮ A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Approximating minimum Manhattan networks in higher dimensions ⋮ Worst-case performance of Wong's Steiner tree heuristic ⋮ On approximating degree-bounded network design problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Inapproximability of survivable networks ⋮ Combinatorial optimization in system configuration design ⋮ Approximating fault-tolerant group-Steiner problems ⋮ Unnamed Item ⋮ The polymatroid Steiner problems ⋮ A greedy approximation algorithm for the group Steiner problem ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications

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