Approximating Directed Weighted-Degree Constrained Networks

DOI10.1007/978-3-540-85363-3_18zbMath1159.68675MaRDI QIDQ3541798

Zeev Nutov

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

Mathematics Subject Classification ID

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