Approximation Algorithms for Network Design with Metric Costs

DOI10.1137/040621806MaRDI QIDQ3519197zbMATH OpenOpenAlexFDO

Authors Adrian Vetta, Joseph Cheriyan

Publication date 13 August 2008

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/040621806

zbMATH Keywords

approximation algorithmedge-connectivitylinear programming relaxationnetwork designvertex-connectivity

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1670542
• Publication:4886063
• Approximating node connectivity problems via set covers
• Degree bounded network design with metric costs
• Approximating survivable networks with \(\beta \)-metric costs

Cited in

(16)

• Approximating node connectivity problems via set covers
• Approximating bounded-degree spanning trees and connected factors with leaves
• Approximation algorithms for connected graph factors of minimum weight
• Approximating subset \(k\)-connectivity problems
• Approximating node-connectivity augmentation problems
• scientific article; zbMATH DE number 1670542 (Why is no real title available?)
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• An improved approximation algorithm for minimum-cost subset k-connectivity (extended abstract)
• scientific article; zbMATH DE number 1532274 (Why is no real title available?)
• Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
• An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
• Survivable network design for group connectivity in low-treewidth graphs
• Approximating survivable networks with \(\beta \)-metric costs
• Approximating some network design problems with node costs
• Network design with edge-connectivity and degree constraints
• A note on Rooted Survivable Networks

This page was built for publication: Approximation Algorithms for Network Design with Metric Costs

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