Content area
Abstract
We consider optimization problems where the main constraint is connectivity. Finding minimum-cost subgraphs with connectivity requirements is a fundamental problem in network optimization. This dissertation focuses on two important problems: the 2-vertex-connectivity problem and the 3-edge-connectivity problem. Improving approximation ratios for k-connectivity problems when k is small is quite a challenge because the problems are easily understood and fundamental, and a lot of researchers have worked on them and many papers have already been published. So, we had to come up with nontrivial algorithms to beat current ratios. Also, one of the uses of approximation algorithms for the above problems is that they can be used as black box algorithms for solving higher connectivity problems. Given a 2-connected graph G = (V, E), the 2-vertex-connected-spanning-subgraph (2VCSS) problem is to find a minimum cardinality subgraph that is also 2-connected. Given a 3-edge-connected graph G(V, E), the 3-edge-connected-spanning-subgraph (3ECSS) problem is to find a minimum cardinality subgraph that is also 3-edge-connected. We also discuss the average- k-VCSS problem and average-k-ECSS problem in this thesis. These problems deal with finding k-connected spanning subgraphs of minimum average weight.
We present different approximation algorithms for edge connectivity and vertex connectivity problems. The following results are discussed in the dissertation: (1) An approximation algorithm with a performance ratio of 9/7 ≈ 1.286 for the 2VCSS problem. (2) An approximation algorithm with a performance ratio of 5/4 for the 2VCSS problem in graphs with a minimum-degree of three at every node. (3) An approximation algorithm with a performance ratio of 4/3 ≈ 1.33 is presented for the 3ECSS problem. (4) A 3-approximation algorithm for the average-k-ECSS problem. (5) An O(logk) approximation algorithm for the average- k-VCSS problem. (6) A 2 + ε approximation algorithm for the average-k-VCSS in Euclidean graphs, for any constant ε > 0. (7) A 3-approximation algorithm for the average- k-VCSS in graphs satisfying the triangle inequality.
