k-Edge-Connectivity: Approximation and LP Relaxation

DOI10.1007/978-3-642-18318-8_20zbMath1314.68402arXiv1004.1917OpenAlexW1752817158MaRDI QIDQ3075464

No author found.

Publication date: 15 February 2011

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.1917

zbMATH Keywords

network designapproximation algorithmsedge-connectivityinapproximabilitylinear programsHeld-Karp relaxation

Mathematics Subject Classification ID

Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (2)

Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs

This page was built for publication: k-Edge-Connectivity: Approximation and LP Relaxation