A unified algorithm for degree bounded survivable network design

DOI10.1007/s10107-015-0858-5zbMath1338.68292OpenAlexW2126340073MaRDI QIDQ896300

Lap Chi Lau, Hong Zhou

Publication date: 9 December 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-015-0858-5

zbMATH Keywords

approximation algorithmgraph theoryminimum bounded degree Steiner network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

A Spectral Approach to Network Design

Cites Work

• On some network design problems with degree constraints
• Network design via iterative rounding of setpair relaxations
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Degree-Constrained Node-Connectivity
• Approximating Minimum-Cost $k$-Node Connected Subgraphs via Independence-Free Graphs
• Iterative Methods in Combinatorial Optimization
• Degree Bounded Matroids and Submodular Flows
• Approximating minimum bounded degree spanning trees to within one of optimal
• Improved Algorithm for Degree Bounded Survivable Network Design Problem
• Survivable Network Design with Degree or Order Constraints
• Additive Guarantees for Degree-Bounded Directed Network Design
• On the L  ∞ -Norm of Extreme Points for Crossing Supermodular Directed Network LPs
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Additive Approximation for Bounded Degree Survivable Network Design

This page was built for publication: A unified algorithm for degree bounded survivable network design