Network Design with Weighted Degree Constraints

DOI10.1007/978-3-642-00202-1_19zbMath1211.68284OpenAlexW1608154347MaRDI QIDQ3605498

Takuro Fukunaga, Hiroshi Nagamochi

Publication date: 24 February 2009

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (2)

Approximating directed weighted-degree constrained networks ⋮ Approximating Directed Weighted-Degree Constrained Networks

Cites Work

• Unnamed Item
• Unnamed Item
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Geometric algorithms and combinatorial optimization
• Spanning trees with minimum weighted degrees
• 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
• Survivable network design with degree or order constraints
• Approximating minimum bounded degree spanning trees to within one of optimal
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• A Push-Relabel Algorithm for Approximating Degree Bounded 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
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Network Design with Weighted Degree Constraints