Network design with weighted degree constraints

DOI10.1016/j.disopt.2010.05.004zbMath1241.90159MaRDI QIDQ429670

Hiroshi Nagamochi, Takuro Fukunaga

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/128835

zbMATH Keywords

connectivity; spanning tree; network design; degree constraint; iterative rounding

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

Related Items

Degree constrained node-connectivity problems, Approximating bounded-degree spanning trees and connected factors with leaves, Approximation algorithms for connected graph factors of minimum weight, Global optimization of multilevel electricity market models including network design and graph partitioning

Cites Work

• Unnamed Item
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
• Geometric algorithms and combinatorial optimization
• Spanning trees with minimum weighted degrees
• What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• Degree Bounded Matroids and Submodular Flows
• Approximating Directed Weighted-Degree Constrained Networks
• Approximating minimum bounded degree spanning trees to within one of optimal
• Survivable Network Design with Degree or Order Constraints
• Additive Guarantees for Degree-Bounded Directed Network Design
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Many birds with one stone
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds