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 (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