Greedy Algorithms for Steiner Forest
From MaRDI portal
Publication:2941584
DOI10.1145/2746539.2746590zbMath1321.68504arXiv1412.7693OpenAlexW2120899253MaRDI QIDQ2941584
Publication date: 21 August 2015
Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.7693
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Flows in graphs (05C21)
Related Items (9)
Approximation algorithms for stochastic combinatorial optimization problems ⋮ Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs ⋮ Approximation algorithms for Steiner forest: An experimental study ⋮ A PTAS for the Steiner Forest Problem in Doubling Metrics ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Stronger MIP formulations for the Steiner forest problem ⋮ An Exact Algorithm for the Steiner Forest Problem ⋮ Approximation of Steiner forest via the bidirected cut relaxation ⋮ On the Complexity of Local Graph Transformations
Uses Software
Cites Work
- Unnamed Item
- Ramsey partitions and proximity data structures
- On sparse spanners of weighted graphs
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- On Approximate Distance Labels and Routing Schemes with Affine Stretch
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Approximate distance oracles
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Shortest-path queries in static networks
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
This page was built for publication: Greedy Algorithms for Steiner Forest
