Approximating directed weighted-degree constrained networks

DOI10.1016/j.tcs.2010.11.043zbMath1211.68018OpenAlexW2053342610MaRDI QIDQ627195

Zeev Nutov

Publication date: 21 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.043

zbMATH Keywords

bicriteria approximation algorithmsdirected network designintersecting supermodular requirementsweighted degree constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

On some network design problems with degree constraints ⋮ Degree constrained node-connectivity problems ⋮ Network-Design with Degree Constraints

Cites Work

• Unnamed Item
• 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

This page was built for publication: Approximating directed weighted-degree constrained networks