Network design with edge-connectivity and degree constraints

DOI10.1007/S00224-008-9149-3MaRDI QIDQ839639zbMATH OpenOpenAlexFDO

Authors Takuro Fukunaga, Hiroshi Nagamochi

Publication date 2 September 2009

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.498.2387

zbMATH Keywords

TSPdegree constraintvehicle routing problemedge-connectivity\((m,n)\)-VRPappproximation algorithm

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Network Design with Edge-Connectivity and Degree Constraints
• Degree bounded network design with metric costs
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Approximation Algorithms for Network Design with Metric Costs
• Survivable network design with degree or order constraints

Cites work

• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• A Reduction Method for Edge-Connectivity in Graphs
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A polynomial algorithm for b-matchings: An alternative approach
• APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
• Applications of approximation algorithms to cooperative games
• Approximating minimum bounded degree spanning trees to within one of optimal
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Heuristic analysis, linear programming and branch and bound
• On a theorem of Mader
• Survivable network design with degree or order constraints
• Survivable networks, linear programming relaxations and the parsimonious property

Cited in

(9)

• Design networks with bounded pairwise distance
• Degree bounded network design with metric costs
• Approximating bounded-degree spanning trees and connected factors with leaves
• Approximation algorithms for connected graph factors of minimum weight
• scientific article; zbMATH DE number 6423757 (Why is no real title available?)
• Network Design with Edge-Connectivity and Degree Constraints
• The phases of large networks with edge and triangle constraints
• scientific article; zbMATH DE number 5176323 (Why is no real title available?)
• APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)

This page was built for publication: Network design with edge-connectivity and degree constraints

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