New primal-dual algorithms for Steiner tree problems
From MaRDI portal
Publication:868154
DOI10.1016/j.cor.2005.08.009zbMath1112.90070OpenAlexW2077745958MaRDI QIDQ868154
Publication date: 19 February 2007
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2005.08.009
Programming involving graphs or networks (90C35) Optimality conditions and duality in mathematical programming (90C46) Combinatorial optimization (90C27) Randomized algorithms (68W20)
Related Items (5)
A Practical Greedy Approximation for the Directed Steiner Tree Problem ⋮ A primal-dual approximation algorithm for the vertex cover \(P^3\) problem ⋮ Subjectively interesting connecting trees and forests ⋮ A Lagrangean-based decomposition approach for the link constrained Steiner tree problem ⋮ The set covering problem revisited: an empirical study of the value of dual information
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A series of approximation algorithms for the acyclic directed Steiner tree problem
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Primal-Dual-Based Algorithms for a Directed Network Design Problem
- A dual ascent approach for steiner tree problems on a directed graph
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Steiner problem in networks: A survey
- A Greedy Heuristic for the Set-Covering Problem
- A linear-time approximation algorithm for the weighted vertex cover problem
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Approximation Algorithms for Directed Steiner Problems
This page was built for publication: New primal-dual algorithms for Steiner tree problems
