Network Design with Weighted Degree Constraints

DOI10.1007/978-3-642-00202-1_19MaRDI QIDQ3605498zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Network design with weighted degree constraints
• Survivable network design problems with weighted degree constraints
• Approximating Directed Weighted-Degree Constrained Networks
• Approximating directed weighted-degree constrained networks
• Approximation algorithms for degree-constrained minimum-cost network-design problems

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• Approximating Directed Weighted-Degree Constrained Networks
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Degree Bounded Matroids and Submodular Flows
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 5485590 (Why is no real title available?)
• scientific article; zbMATH DE number 5485591 (Why is no real title available?)
• Many birds with one stone
• Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
• Spanning trees with minimum weighted degrees
• Survivable network design with degree or order constraints

Cited in

(8)

• Design networks with bounded pairwise distance
• Survivable network design problems with weighted degree constraints
• Approximating Directed Weighted-Degree Constrained Networks
• Network design with weighted degree constraints
• Node-weighted Network Design in Planar and Minor-closed Families of Graphs
• Network Design with Edge-Connectivity and Degree Constraints
• Approximating directed weighted-degree constrained networks
• Network design with weighted players

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3605498)