Development of algorithms for solving graph/network problems

在本研究中，我们发展了有效的图演算法，并厘清了图/网路问题中的图结构。我们已经改善了时间复杂度表示所有最小割仙人掌。为了实现这一点，我们使用了最大邻接排序，一个图搜索过程，通过它可以找到所有的最小切割，而不使用最大流算法。一个边的子集被称为k-割，如果删除它的结果是k个组件。本文采用一种新的方法，即按权重的非递减顺序列举2-割，从而减少了计算k= 3，4，5，6的最小k-割的时间界限。我们已经证明，必要的信息，以解决k-边连通性增强问题，可以从一个适当的一组大小小于k在一个给定的图的削减提取。利用这一割集，我们可以控制边连通性扩充问题解的结构，并在设计近似算法时得到了如下结果。针对目标值为k的点连通度问题，提出了一个仅适用于给定图为（k-1）-点连通的近似算法.我们扩展算法，使其适用于任意输入图。我们的算法提供了一个绝对误差为2（α-k）k的解决方案，其中α =输入图的顶点连通度。本文研究了边连通度和顶点连通度同时增加的问题，给出了一个绝对误差只依赖于目标值的近似算法。对于d度超图中的加权3-点连通性扩充问题，我们设计了一个（7/2）-近似算法，一个2-近似算法，一个dH（r）-近似算法，其中r是最大需求，H（）是调和函数。

In this research, we have developed efficient graph algorithms and clarified graph structures in the graph/network problems.We have obtained the following results for the problems related to connectivity. We have improved the time complexity for representing all minimum cuts in a cactus. To achieve this, we used a maximum adjacency ordering, a graph search procedure by which all minimum cuts can be found without using the maximum-flow algorithm. A subset of edges is called a k-cut if removal of it results in k components. We have reduced the time bound for computing a minimum k-cut for k=3,4,5,6 by a new approach that enumerates 2-cut in the nondecreasing order of weights. We have proved that necessary information to solve the k-edge-connectivity augmentation problem can be extracted from an appropriate set of cuts with size less than k in a given graph. By using such a set of cuts, we can control structure of solutions to the edge-connectivity augmentation problem.We have also obtained the following results in designing approximation algorithms. For the vertex-connectivity problem with a target value k, an approximation algorithm was proposed only for the case where a given graph is (k-1)-vertex-connected. We extend the algorithm so that it works for an arbitrary input graph. Our algorithm delivers an solution with absolute error 2(α-k)k, where α =the vertex-connectivity of an input graph. We have studied the problem of increasing the edge- and vertex-connectivities at the same time, and gave an approximation algorithm with absolute error that depends only on the target values. We have also designed a (7/2)-approximation algorithm for the weighted 3-vertex-connectivity augmentation problem, a 2-approximation algorithm for the weighted minimum edge dominating set problem and a dH(r)-approximation algorithm for the network design problem in hypergraph with degree d, where r is the maximum demand and H() is the harmonic function.