Survivable network design with degree or order constraints

DOI10.1137/070700620MaRDI QIDQ3575159zbMATH OpenOpenAlexFDO

Authors Lap Chi Lau, Joseph (Seffi) Naor, Mohammad 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

zbMATH Keywords

approximation algorithmssurvivable network design\(k\)-subgraph\(\lambda\)-edge-connecteddegree bounded

Mathematics Subject Classification ID

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

Recommendations

• Additive Approximation for Bounded Degree Survivable Network Design
• Degree bounded network design with metric costs
• Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
• A unified algorithm for degree bounded survivable network design
• Improved algorithm for degree bounded survivable network design problem

Cited in

(36)

• Approximating bounded-degree spanning trees and connected factors with leaves
• Approximation algorithms for connected graph factors of minimum weight
• Improved algorithm for degree bounded survivable network design problem
• Network-design with degree constraints
• Degree-constrained node-connectivity
• Approximating minimum bounded degree spanning trees to within one of optimal
• The maximum binary tree problem
• Network design with edge-connectivity and degree constraints
• On some network design problems with degree constraints
• Sensor fault detection and isolation via networked estimation: rank-deficient dynamical systems
• Network design with weighted degree constraints
• Fast exact algorithms for survivable network design with uniform requirements
• Improved approximation algorithms for maximum lifetime problems in wireless networks
• Binary Steiner trees: structural results and an exact solution approach
• Pruning 2-connected graphs
• A unified algorithm for degree bounded survivable network design
• On approximating degree-bounded network design problems
• The complexity of optimal design of temporally connected graphs
• The minimum degree group Steiner problem
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Additive Approximation for Bounded Degree Survivable Network Design
• On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
• Survivable network design with demand uncertainty
• Approximation algorithms for finding low-degree subgraphs
• Degree constrained node-connectivity problems
• On approximating degree-bounded network design problems
• A Spectral Approach to Network Design
• Approximation algorithms for \(k\)-connected graph factors
• Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
• A simple LP relaxation for the asymmetric traveling salesman problem
• Parameterized algorithms for survivable network design with uniform demands
• Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph
• Survivable network design problems with weighted degree constraints
• Degree bounded network design with metric costs
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• Multicommodity flow in trees: packing via covering and iterated relaxation

This page was built for publication: Survivable network design with degree or order constraints

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