Survivable network design with degree or order constraints

DOI10.1145/1250790.1250886zbMath1232.68182OpenAlexW2055155874MaRDI QIDQ3549666

Mohammad R. Salavatipour, Joseph (Seffi) Naor, Mohit Singh, Lap Chi Lau

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

zbMATH Keywords

approximation algorithmssurvivable network design\(k\)-subgraph\(\lambda\)-edge-connecteddegree boundedminimum bounded degree spanning treeminimum bounded degree Steiner forest

Mathematics Subject Classification ID

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

Related Items (14)

Network design with edge-connectivity and degree constraints ⋮ Approximation Algorithms for Multi-budgeted Network Design Problems ⋮ New approaches to multi-objective optimization ⋮ Approximating directed weighted-degree constrained networks ⋮ Pruning 2-connected graphs ⋮ Degree bounded matroids and submodular flows ⋮ A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem ⋮ Approximating Directed Weighted-Degree Constrained Networks ⋮ Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees ⋮ Network Design with Weighted Degree Constraints ⋮ A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs ⋮ Approximating fault-tolerant group-Steiner problems ⋮ A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids ⋮ Unnamed Item

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