Construction of Approximation Algorithms Based on Graph Theory and Its Application to Network Problems

利用最大邻接序的稀疏化技术，得到了<n>求图G的最小点割问题的2-近似解的O（n^2（1+min{κ^2，κ}/δ））时间和O（-n+m）空间算法，其中n，m，κ和δ分别表示图G的顶点数，边数，点连通度和最小度.对于具有源s和汇t的有向图的最小（s，t）-割问题，引入了一个新的参数μ来度量给定有向图的无向性，并给出了一个O（min{m+ v（v +μ）^&lt;1/2&gt;n，（v +μ）^&lt;1/6&gt;nm^&lt;2/3&gt;}}）时间算法，其中v表示最小（s，t）-割的大小.对于扩充给定连通图以满足指定对之间的双连通性问题，我们设计了一个线性时间4/3近似算法，并综述了网络连通性问题的图算法的最新进展。我们证明了利用最大邻接序可以在O（mn+ n^2logn）时间内解决极值集问题、仙人掌表示问题、边连通性扩充问题和源定位问题。

By using sparsification technique by maximum adjacency order, we obtained an O(n^2(1+min{κ^2, κ√<n>}/δ)) time and O(-n+m) space algorithm that computes a 2-approximation solution for the problem of finding a minimum vertex cut in a graph G, where n,m,κ and δ denote the number of vertices, the number of edges, the vertex-connectivity and the minimum degree in G, respectively.For the problem of finding a minimum (s,t)-cut in a digraph with a source s and a sink t, we introduced a new parameter μ that measures undirectedness of a given digraph, and gave an O(min{m+ν(ν+μ)^<1/2>n,(ν+μ)^<1/6>nm^<2/3>}}) time algorithm, where ν denotes the size of a minimum (s,t)-cut.For the problem of augmenting a given connected graph to meet biconnectivity between a prescribed pair, we designed a linear time 4/3-approximation algorithm.We also surveyed a recent progress on graph algorithms for network connectivity problems. We showed that the extreme set problem, the cactus representation problem, the edge-connectivity augmentation problem and the source location problem can be solved in O(mn+n^2log n) time by using maximum adjacency order.