Survivable network design with degree or order constraints
DOI10.1145/1250790.1250886zbMATH Open1232.68182OpenAlexW2055155874MaRDI QIDQ3549666FDOQ3549666
Authors: Lap Chi Lau, Joseph (Seffi) Naor, Mohammad Salavatipour, Mohit Singh 
Publication date: 5 January 2009
Published in: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1250790.1250886
approximation algorithmssurvivable network design\(k\)-subgraph\(\lambda\)-edge-connecteddegree boundedminimum bounded degree spanning treeminimum bounded degree Steiner forest
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25)
Cited In (14)
- A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
- New approaches to multi-objective optimization
- Network design with edge-connectivity and degree constraints
- Network Design with Weighted Degree Constraints
- Pruning 2-connected graphs
- Approximation algorithms for multi-budgeted network design problems
- A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
- Approximating Directed Weighted-Degree Constrained Networks
- Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
- Matroidal degree-bounded minimum spanning trees
- Approximating fault-tolerant group-Steiner problems
- Approximating directed weighted-degree constrained networks
- Degree bounded matroids and submodular flows
- A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem
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 Q3549666)
