Development of algorithms for solving graph/network problems

开发解决图/网络问题的算法

• 批准号: 10205213
• 负责人: NAGAMOCHI Hiroshi
• 金额: $ 6.4万
• 依托单位: Toyohashi University of Technology (TUT) (2000-2001)Kyoto University (1998-1999)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205213/
• 关键词: graph algorithm; minimum cut; connectivity; combinatorial optimization; combinatorial optimization game; graph partition; approximation algorithm; connectivity augmentation; 離散最適化; ネットワーク問題; 最小カット問題; 協力ゲーム; グラフ連結度; 劣モジュール関数; アルゴリズム; グラフ・ネット

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.

在这项研究中，我们开发了高效的图算法，并阐明了图/网络问题中的图结构。我们改进了表示仙人掌中所有最小切割的时间复杂度。为了实现这一点，我们使用了最大邻接排序，这是一种图搜索过程，通过它可以找到所有的最小割线，而不需要使用最大流算法。如果去除边子集得到k个分量，则称其为k-割。我们通过一种新的方法减少了计算k=3，4，5，6的最小k-割的时间界限，该方法以非降序的方式计数2-割。我们已经证明了解决k-边连通性增强问题所需的信息可以从给定图中长度小于k的适当割集中提取。利用这样的割集，我们可以控制边连通性增强问题的解的结构。在设计近似算法方面，我们还得到了以下结果。对于目标值为k的顶点连通性问题，仅当给定的图是(k-1)点连通的情况下，才提出了一种近似算法。我们对算法进行了扩展，使其适用于任意输入图。我们的算法提供了一个绝对误差为2(α-k)k的解，其中α=输入图的顶点连通性。研究了同时增加边连通度和顶点连通度的问题，给出了一种只依赖目标值的绝对误差近似算法。我们还设计了加权3点连通性增强问题的(7/2)近似算法、加权最小边支配集问题的2近似算法和d度超图中网络设计问题的dH(R)近似算法，其中r是最大需求，H()是调和函数。

项目成果

Y.Karuno: "A 1.5-approximation for single-vehicle scheduling problem on a line with release and handling times"Japan-U.S.A.Symposium on Flexible Automation. 1363-1366 (1998)

Y.Karuno：“A 1.5-approximation for single-vehicle Scheduling Problem on a line with release and Handling times”日本-美国灵活自动化研讨会。

H.Nagamochi: "A note on minimizing submodular functions"Information Processing Letters. vol.67. 239-244 (1988)

H.Nagamochi：“关于最小化子模函数的说明”信息处理快报。

H.Nagamochi: "An approximation of the minimum vertex cover in a graph"J.of Japan Society for Industrial and Applied Mathematics. vol.16,no.3. 369-375 (1999)

H.Nagamochi：“图中最小顶点覆盖的近似”，日本工业与应用数学学会杂志。

P.Eades: "Drawing clustered graphs on an orthogonal grid"Journal of Graph Algorithms and Application. vol.3,no.4. 3-29 (1999)

P.Eades：“在正交网格上绘制聚类图”图算法与应用杂志。

L.Zhao: "Approximating the minimum k-way cut in a graph via minimum 3-way cuts"J.Combinatorial Optimization. vol.5. 397-410 (2001)

L.Zhao：“通过最小 3 路切割近似图中的最小 k 路切割”J.组合优化。