A Practical Greedy Approximation for the Directed Steiner Tree Problem
From MaRDI portal
Publication:2942396
DOI10.1007/978-3-319-12691-3_16zbMath1431.90167MaRDI QIDQ2942396
Marc-Antoine Weisser, Dimitri Watel
Publication date: 11 September 2015
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (2)
A practical greedy approximation for the directed Steiner tree problem ⋮ Subjectively interesting connecting trees and forests
Cites Work
- Unnamed Item
- Unnamed Item
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- New primal-dual algorithms for Steiner tree problems
- A fast algorithm for Steiner trees
- An 11/6-approximation algorithm for the network Steiner problem
- An improved approximation scheme for the Group Steiner Problem
- Contraction-Based Steiner Tree Approximations in Practice
- A threshold of ln n for approximating set cover
- A dual ascent approach for steiner tree problems on a directed graph
- Polylogarithmic inapproximability
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for Directed Steiner Problems
- Reducibility among Combinatorial Problems
- A distributed dual ascent algorithm for Steiner problems in multicast routing
- Fast Local Search for Steiner Trees in Graphs
- Steiner Tree Approximation via Iterative Randomized Rounding
- A note on distributed multicast routing in point-to-point networks
This page was built for publication: A Practical Greedy Approximation for the Directed Steiner Tree Problem
