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

基于图论的逼近算法构建及其在网络问题中的应用

• 批准号: 14580372
• 负责人: NAGAMOCHI Hiroshi
• 金额: $ 2.24万
• 依托单位: Kyoto University (2004)Toyohashi University of Technology (2002-2003)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14580372/
• 关键词: graph connectivity; polynomial algorithm; approximation algorithm; network problem; maximum flow problem; vertex connectivity; edge connectivity; maximum adjacency order; スケジューリング問題; 矩形分割問題; 供給点配置問題; 連結度増大問題; 耐故障性; ネットワークトポロジー; グラフ理論; ネットワー

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.

利用最大邻接序稀疏技术，得到了O(n^2(1+min{κ^2，κ√&lt；n&gt；}/δ)时间和O(-n+m)空间算法计算图G的最小顶点割问题的2-近似解，其中n，m，κ和δ分别表示图G中的点数、边数、点连通度和最小度.对于具有源S和汇t的有向图的最小(S，t)割问题，我们引入了一个新的参数μ来度量给定有向图的无向度，并给出了一个O(min{m+ν(ν+μ)^&lt；1/2&gt；N，(ν+μ)^&lt；1/6&gt；nm^&lt；2/3&gt；}})时间算法，其中ν表示最小(S，t)割的大小。对于扩充给定的连通图以满足指定对之间的双连通性的问题，我们设计了一个线性时间4/3近似算法。证明了极值集问题、仙人掌表示问题、边连通性增广问题和信源定位问题可以用最大邻接阶数在O(n+n^2logn)时间内得到解决。

项目成果

H.Nagamocihi, P.Eades: "An edge-splitting algorithm in planar graphs"J. Combinatorial Optimization. (掲載決定).

H.Nagamocihi、P.Eades：“平面图中的边缘分割算法”J. 组合优化。

Y.Karuno, H.Nagamochi: "A better approximation for the two-stage assembly scheduling problem with 2 machines at the first stage"Lecture Notes in Computer Science. voo.2518. 199-210 (2002)

Y.Karuno、H.Nagamochi：“第一阶段有 2 台机器的两阶段装配调度问题的更好近似”计算机科学讲义。

A simple recognition of maximal planar graphs

最大平面图的简单识别

• 发表时间: 2004
• 期刊: Information Processing Letters 89・5
• 作者: H.Nagamochi;K.Suzuki;T.Ishii
• 通讯作者: T.Ishii

Augmenting a (k-1)-vertex-connected multigraph to an l-edge-connected and k-vertex-connected multigraph

将 (k-1) 顶点连接的多重图增强为 l 边连接和 k 顶点连接的多重图

• 期刊: Algorithmica (to appear)
• 作者: T.Ishii;H.Nagamochi;T.Ibaraki
• 通讯作者: T.Ibaraki

T.Ishii, H.Fujita, H.Nagamochi: "Source location problem with local 3-vertex-connectivity requirements"The 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications. 368-377 (2003)

T.Ishii、H.Fujita、H.Nagamochi：“具有局部 3 顶点连通性要求的源定位问题”第三届匈牙利-日本离散数学及其应用研讨会。