Approximating Directed Weighted-Degree Constrained Networks
From MaRDI portal
Publication:3541798
DOI10.1007/978-3-540-85363-3_18zbMath1159.68675MaRDI 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
90C35: Programming involving graphs or networks
90C27: Combinatorial optimization
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
On generalizations of network design problems with degree bounds, Network design with weighted degree constraints, Improved approximation algorithms for maximum lifetime problems in wireless networks, On approximating the \(d\)-girth of a graph, On Approximating the d-Girth of a Graph, Network Design with Weighted Degree Constraints
Cites Work
- Unnamed Item
- Unnamed Item
- 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