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

通过使用最大邻接顺序稀疏化技术，我们获得了O（n^2(1+min{κ^2, κ√<n>}/δ)）时间和O（-n+m）空间算法，用于计算图G中寻找最小顶点切割问题的2逼近解，其中n，m，κ和δ分别表示顶点数，边数，顶点连通性和G中的最小度。针对有向图的最小（s,t）切口的求解问题，引入了一个新的参数μ来度量给定有向图的无向性，并给出了一个O(min{m+ν(ν+μ)^<1/2>n,(ν+μ)^<1/6>nm^<2/3>}})时间算法，其中ν表示最小（s,t）切口的大小。对于给定连通图的增广以满足给定对之间的双连通问题，我们设计了一个线性时间4/3逼近算法。我们还调查了网络连接问题的图算法的最新进展。结果表明，利用最大邻接顺序可以在O（mn+n^2log n）时间内解决极值集问题、仙人掌表示问题、边连通性增强问题和源定位问题。

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.