Additive Approximation for Bounded Degree Survivable Network Design

DOI10.1137/110854461zbMath1285.68216OpenAlexW2058605762MaRDI QIDQ5408765

Mohit Singh, Lap Chi Lau

Publication date: 11 April 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110854461

zbMATH Keywords

linear programmingapproximation algorithmssurvivable network designSteiner forestiterative relaxation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (8)

On approximating degree-bounded network design problems ⋮ The complexity of optimal design of temporally connected graphs ⋮ A Spectral Approach to Network Design ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ A unified algorithm for degree bounded survivable network design ⋮ Approximating bounded-degree spanning trees and connected factors with leaves ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ On approximating degree-bounded network design problems

This page was built for publication: Additive Approximation for Bounded Degree Survivable Network Design