Network design with edge-connectivity and degree constraints

DOI10.1007/s00224-008-9149-3zbMath1192.68895OpenAlexW2151121203MaRDI QIDQ839639

Hiroshi Nagamochi, Takuro Fukunaga

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

TSPvehicle routing problemedge-connectivitydegree constraint\((m,n)\)-VRPappproximation algorithm

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items (2)

Approximating bounded-degree spanning trees and connected factors with leaves ⋮ Approximation algorithms for connected graph factors of minimum weight

Cites Work

• Unnamed Item
• Survivable networks, linear programming relaxations and the parsimonious property
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A polynomial algorithm for b-matchings: An alternative approach
• On a theorem of Mader
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Survivable network design with degree or order constraints
• Approximating minimum bounded degree spanning trees to within one of optimal
• Heuristic analysis, linear programming and branch and bound
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• A Reduction Method for Edge-Connectivity in Graphs
• A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
• Applications of approximation algorithms to cooperative games
• 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