Survivable network design with degree or order constraints

DOI10.1145/1250790.1250886MaRDI QIDQ3549666zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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
• Pruning 2-connected graphs
• Network Design with Weighted Degree Constraints
• 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)