Return to search

Approximation Algorithms for (S,T)-Connectivity Problems

We study a directed network design problem called the $k$-$(S,T)$-connectivity problem; we design and analyze approximation
algorithms and give hardness results. For each positive integer $k$, the minimum cost $k$-vertex connected spanning subgraph problem is a special case of the $k$-$(S,T)$-connectivity problem. We defer
precise statements of the problem and of our results to the introduction.

For $k=1$, we call the problem the $(S,T)$-connectivity problem. We study three variants of the problem: the standard
$(S,T)$-connectivity problem, the relaxed $(S,T)$-connectivity problem, and the unrestricted $(S,T)$-connectivity problem. We give hardness results for these three variants. We design a $2$-approximation algorithm for the standard $(S,T)$-connectivity problem. We design tight approximation algorithms for the relaxed $(S,T)$-connectivity problem and one of its special cases.

For any $k$, we give an $O(\log k\log n)$-approximation algorithm,
where $n$ denotes the number of vertices. The approximation guarantee
almost matches the best approximation guarantee known for the minimum
cost $k$-vertex connected spanning subgraph problem which is $O(\log
k\log\frac{n}{n-k})$ due to Nutov in 2009.

Identiferoai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/5321
Date27 July 2010
CreatorsLaekhanukit, Bundit
Source SetsUniversity of Waterloo Electronic Theses Repository
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation

Page generated in 0.0018 seconds