A practical greedy approximation for the directed Steiner tree problem
From MaRDI portal
Publication:346528
DOI10.1007/S10878-016-0074-0zbMath1356.90151OpenAlexW2518649733MaRDI QIDQ346528
Dimitri Watel, Marc-Antoine Weisser
Publication date: 29 November 2016
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-016-0074-0
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (4)
A linear programming based approach to the Steiner tree problem with a fixed number of terminals ⋮ Heuristic and exact algorithms for minimum-weight non-spanning arborescences ⋮ Navigational guidance -- a deep learning approach ⋮ Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
Uses Software
Cites Work
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- 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
- A Practical Greedy Approximation for the Directed Steiner Tree 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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A practical greedy approximation for the directed Steiner tree problem
