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个组件。本文采用一种新的方法，即按权重的非递减顺序列举2-割，从而减少了计算k= 3，4，5，6的最小k-割的时间界限。我们已经证明，必要的信息，以解决k-边连通性增强问题，可以从一个适当的一组大小小于k在一个给定的图的削减提取。利用这一割集，我们可以控制边连通性扩充问题解的结构，并在设计近似算法时得到了如下结果。针对目标值为k的点连通度问题，提出了一个仅适用于给定图为（k-1）-点连通的近似算法.我们扩展算法，使其适用于任意输入图。我们的算法提供了一个绝对误差为2（α-k）k的解决方案，其中α =输入图的顶点连通度。本文研究了边连通度和顶点连通度同时增加的问题，给出了一个绝对误差只依赖于目标值的近似算法。对于d度超图中的加权3-点连通性扩充问题，我们设计了一个（7/2）-近似算法，一个2-近似算法，一个dH（r）-近似算法，其中r是最大需求，H（）是调和函数。

项目成果

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

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

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: "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.组合优化。