Development of algorithms for solving graph/network problems

在本研究中，我们开发了高效的图算法，并澄清了图/网络问题中的图结构。关于连通性的问题，我们得到了如下的结果。我们改进了表示仙人掌中所有最小切口的时间复杂度。为了实现这一点，我们使用了最大邻接排序，这是一个图搜索过程，通过该过程可以找到所有最小切割，而无需使用最大流量算法。如果一个边的子集被移除会产生k个分量，那么这个子集就被称为k-cut。我们已经减少了计算k=3,4,5,6的最小k-cut的时间限制，通过一种新的方法，以权重的非递减顺序枚举2-cut。我们证明了在给定的图中，可以从一个大小小于k的合适的切集中提取出解决k边连通性增强问题所需的信息。通过使用这样的切集，我们可以控制边缘连通性增强问题的解的结构。在设计近似算法时，我们也得到了以下结果。对于目标值为k的顶点连通性问题，仅在给定图为（k-1）顶点连通的情况下，提出了一种近似算法。我们扩展了该算法，使其适用于任意输入图。我们的算法提供了一个绝对误差为2(α-k)k的解决方案，其中α =输入图的顶点连通性。研究了边连通性和顶点连通性同时增加的问题，给出了一种只依赖于目标值的绝对误差近似算法。我们还设计了加权3点连通性增强问题的（7/2）逼近算法，加权最小边支配集问题的2-逼近算法和d次超图中网络设计问题的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.