Approximating Directed Weighted-Degree Constrained Networks

DOI10.1007/978-3-540-85363-3_18zbMath1159.68675OpenAlexW1830269881MaRDI 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

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

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