License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09511.4
URN: urn:nbn:de:0030-drops-24975
Go to the corresponding Portal

Kortsarz, Guy ; Nutov, Zeev

Approximating minimum cost connectivity problems

09511.KortsarzGuy.Paper.2497.pdf (0.3 MB)


We survey approximation algorithms of connectivity problems.
The survey presented describing various techniques. In the talk the following techniques and results are presented.

1)Outconnectivity: Its well known that there exists a polynomial time algorithm to solve the problems of finding an edge k-outconnected from r subgraph [EDMONDS] and a vertex k-outconnectivity subgraph from r [Frank-Tardos] .
We show how to use this to obtain a ratio 2 approximation for the min cost edge k-connectivity

2)The critical cycle theorem of Mader: We state a fundamental theorem of Mader and use it to provide a 1+(k-1)/n ratio approximation for the min cost vertex k-connected subgraph, in the metric case.
We also show results for the min power vertex k-connected problem using this lemma.
We show that the min power is equivalent to the min-cost case with respect to approximation.

3)Laminarity and uncrossing: We use the well known laminarity of a BFS solution and show a simple new proof due to Ravi et al for Jain's 2 approximation for Steiner network.

BibTeX - Entry

  author =	{Kortsarz, Guy and Nutov, Zeev},
  title =	{{Approximating minimum cost connectivity problems}},
  booktitle =	{Parameterized complexity and approximation algorithms},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9511},
  editor =	{Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-24975},
  doi =		{10.4230/DagSemProc.09511.4},
  annote =	{Keywords: Connectivity, laminar, uncrossing, Mader's Theorem, power problems}

Keywords: Connectivity, laminar, uncrossing, Mader's Theorem, power problems
Collection: 09511 - Parameterized complexity and approximation algorithms
Issue Date: 2010
Date of publication: 02.03.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI