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

DOI10.1007/BF02523690zbMATH Open0873.68079OpenAlexW2005771129MaRDI QIDQ679453FDOQ679453

Authors: Alex 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

Recommendations

• Approximation Algorithms for Directed Steiner Problems
• scientific article; zbMATH DE number 1303557
• scientific article; zbMATH DE number 2119644
• Multi-rooted greedy approximation of directed Steiner trees with applications
• Multi-rooted greedy approximation of directed Steiner trees with applications

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)

Cites Work

• An 11/6-approximation algorithm for the network Steiner problem
• The Steiner tree problem
• Title not available (Why is that?)
• On the hardness of approximating minimization problems
• The rectilinear Steiner arborescence problem
• Title not available (Why is that?)
• A faster approximation algorithm for the Steiner problem in graphs
• The Steiner problem with edge lengths 1 and 2
• The computation of nearly minimal Steiner trees in graphs
• Worst-case performance of Rayward-Smith's Steiner tree heuristic
• Title not available (Why is that?)
• Cost-minimal trees in directed acyclic graphs

Cited In (33)

• Title not available (Why is that?)
• Multi-rooted greedy approximation of directed Steiner trees with applications
• Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• Improved approximation algorithms for directed Steiner forest
• Inapproximability of survivable networks
• An improved approximation scheme for the Group Steiner Problem
• Online Buy-at-Bulk Network Design
• On approximating degree-bounded network design problems
• Title not available (Why is that?)
• Parameterized complexity of directed Steiner tree on sparse graphs
• Title not available (Why is that?)
• Worst-case performance of Wong's Steiner tree heuristic
• Combinatorial optimization in system configuration design
• The polymatroid Steiner problems
• A greedy approximation algorithm for the group Steiner problem
• An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
• A practical greedy approximation for the directed Steiner tree problem
• A practical greedy approximation for the directed Steiner tree problem
• Directed Steiner trees with diffusion costs
• On approximating degree-bounded network design problems
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
• Register loading via linear programming
• Parameterized algorithms for the Steiner arborescence problem on a hypercube
• Approximating fault-tolerant group-Steiner problems
• New primal-dual algorithms for Steiner tree problems
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
• Navigational guidance -- a deep learning approach
• Combination algorithms for Steiner tree variants
• Bounded Degree Group Steiner Tree Problems
• A layered graph model and an adaptive layers framework to solve delay-constrained minimum tree problems
• $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
• Approximation Algorithms for Directed Steiner Problems

This page was built for publication: A series of approximation algorithms for the acyclic directed Steiner tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679453)