Approximating Directed Weighted-Degree Constrained Networks
From MaRDI portal
Publication:3541798
DOI10.1007/978-3-540-85363-3_18zbMath1159.68675OpenAlexW1830269881MaRDI QIDQ3541798
Publication date: 27 November 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_18
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (6)
On generalizations of network design problems with degree bounds ⋮ Network design with weighted degree constraints ⋮ On approximating the \(d\)-girth of a graph ⋮ Improved approximation algorithms for maximum lifetime problems in wireless networks ⋮ Network Design with Weighted Degree Constraints ⋮ On Approximating the d-Girth of a Graph
Cites Work
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- Survivable network design with degree or order constraints
- Approximating minimum bounded degree spanning trees to within one of optimal
- Network Design with Weighted Degree Constraints
- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Algorithms for a network design problem with crossing supermodular demands
- Small degree out‐branchings
- Many birds with one stone
- Unnamed Item
- Unnamed Item
This page was built for publication: Approximating Directed Weighted-Degree Constrained Networks