Approximation Algorithms For Finding Highly Connected Subgraphs

The problem of finding highly connected subgraphs is an urgent problem that is very difficult in computation theory, but has been widely used in practice. Two problems of finding edge-connected subgraphs and vertex-connected subgraphs are studied from the aspects of mathematical model of optimization. According to the natures of finding highly connected subgraphs, several approximation algorithms are presented.First several algorithms are presented for the simple 2-edge-connected subgraphs. Based on the idea of depth first search and by means of the maximum spanning tree, a depth first algorithm are presented. The algorithm is simple, manageable and fast. For the complex graphs,"D2"(Degree 2) algorithm is effective. Do some preprocessing first, simplify the graphs and make use of the maximum braches to obtain a solution. And the approximation ration is improved. The removing-edge algorithm is absolutely different from the previous two. It introduces the idea of removing edges. It breaks up the original graph, then adds vertexes and removes edges to get 2-edge-connected spanning subgraphs. Experiment shows it would be more effective for simple graphs. Finally, combining the depth first algorithm and the idea of the algorithm given by Nagamochi和Ibaraki, one effective algorithm forλ? edge-connected subgraphs is obtained.Some algorithms are presented for 2-vertex-connected subgraphs. Based on the depth first algorithm for 2-edge-connected subgraphs, the depth first algorithm for 2-vertex-connected subgraphs is obtained by slight changes. And the algorithm is improved by some changes to improving the approximation ration. Based on the"D2"algorithm for 2-edge-connected subgraphs, using the similar idea and approximation algorithm for 2-vertex-connected subgraphs is obtained.At last, all the works in this thesis are summarized and some prospects are proposed.