Approximation Algorithms for Network Design with Metric Costs

DOI10.1137/040621806zbMath1154.68110OpenAlexW2079430060MaRDI QIDQ3519197

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 algorithmnetwork designlinear programming relaxationedge-connectivityvertex-connectivity

Mathematics Subject Classification ID

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

Related Items (9)

Approximating subset \(k\)-connectivity problems ⋮ Approximating node-connectivity augmentation problems ⋮ Unnamed Item ⋮ Approximating bounded-degree spanning trees and connected factors with leaves ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity ⋮ Approximating survivable networks with \(\beta \)-metric costs ⋮ A note on Rooted Survivable Networks

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