Survivable Network Design with Degree or Order Constraints
From MaRDI portal
Publication:3575159
DOI10.1137/070700620zbMath1192.68911OpenAlexW2161190897MaRDI QIDQ3575159
Joseph (Seffi) Naor, Lap Chi Lau, Mohammad R. Salavatipour, Mohit Singh
Publication date: 7 July 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070700620
approximation algorithmssurvivable network design\(k\)-subgraph\(\lambda\)-edge-connecteddegree bounded
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (24)
On approximating degree-bounded network design problems ⋮ On some network design problems with degree constraints ⋮ The complexity of optimal design of temporally connected graphs ⋮ On generalizations of network design problems with degree bounds ⋮ A simple LP relaxation for the asymmetric traveling salesman problem ⋮ A Spectral Approach to Network Design ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Sensor fault detection and isolation via networked estimation: rank-deficient dynamical systems ⋮ A unified algorithm for degree bounded survivable network design ⋮ Pruning 2-connected graphs ⋮ Network design with weighted degree constraints ⋮ Approximating bounded-degree spanning trees and connected factors with leaves ⋮ Degree constrained node-connectivity problems ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ Binary Steiner trees: structural results and an exact solution approach ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ On approximating degree-bounded network design problems ⋮ Improved approximation algorithms for maximum lifetime problems in wireless networks ⋮ On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ The maximum binary tree problem ⋮ Network-Design with Degree Constraints ⋮ The minimum degree group Steiner problem ⋮ Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
This page was built for publication: Survivable Network Design with Degree or Order Constraints
