耐故障性を考慮したネットワーク設計問題に関するグラフアルゴリズムの研究

考虑容错的网络设计问题的图算法研究

• 批准号: 17700011
• 负责人: 石井 利昌
• 金额: $ 2.18万
• 依托单位: Otaru University of Commerce (2006-2007)Toyohashi University of Technology (2005)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17700011/
• 关键词: 組合せ最適化; アルゴリズム; ネットワーク設計; グラフ理論; グラフ連結度; 多項式時間アルゴリズム; 近似アルゴリズム; ネットワーク設計データ構造; データ構造; 連結度; グラフ分割

通信網・交通網,VLSIの配線,施設配置問題など現実社会において解決が求められる多くの問題が,グラフ・ネットワーク的構造を持つ組合せ最適化問題として定式化される.グラフ理論における連結度の概念は,種々のネットワークの制御・設計において,耐故障性に関する基本的な評価尺度として用いられる.本研究では,特に連結度制約を持つネットワーク設計問題を中心に,それらを解く効率的なアルゴリズムを構築することを目的とする.本年度は,これまで申請者が携わってきた,辺の付加により与えられた連結度要求を満たすようにグラフを増大させる連結度増大問題や,連結度要求を満たすように節点上に特別な施設(供給点)の集合を配置する供給点配置問題に対する効率的なアルゴリズムの研究をさらに推し進め,いくつかの結果を得た.例えば,点連結度要求を持つ供給点配置問題の近似可能性に関して次の結果を得た.・無向グラフG=(V, E),関数c: V→R^+,関数d: V→Z^+が与えられたとき,各節点v∈VとSの間にv以外の節点を共有しないパスがd(v)本以上存在し,Σ_<v∈>vc(v)が最小である節点集合Sを求める問題に対し,cが一様の場合,max{d^*, 2d^*-6}倍近似可能であることを証明した.ただし,d^*=max{d(v) | v∈V}である.この問題は、これまで,P=NPでない限り,ある定数cに対してcln(Σ_<v∈>vd(v))倍より良い近似ができないことが知られている.また,cが一様かつ,d^*が定数のときでさえ,問題はNP困難であることが知られている.本研究の成果により,d^*が定数の場合は,cが一様であれば定数倍近似可能であることを示した.また,d^*が定数の場合でもAPX困難であることも示した.

在现实生活中需要解决的许多问题，例如沟通网络和运输网络，VLSI接线和设施放置问题，被称为与图形结构结构的组合优化问题，将连接中的连接概念用作基本的评估量表，用于在各种网络中构建各种问题的范围。限制。本年，我们进一步对有效算法进行了研究，以增加连接程度问题的增加图表，以满足通过添加边缘给出的链接要求，以及在节点上放置特殊设施（供应点）以满足链接要求的节点上的特殊设施（供应点），并获得了几个结果的供应量的问题。 g =（v，e），函数c：v→r^+，函数d：给定v→z^+，我们已经证明，对于在每个节点v∈V和s之间找到节点设置s的问题，其中有超过d（v）路径的d（v）路径超过v，而其他v除了其他v，而不是σ_<vc vc（v），则可能是c^imax and Max and Max， 制服。但是，d^*= max {d（v）| v∈V}。众所周知，除非p = np，否则不能比给定常数的cln（σ_<v∈> vd（v））次数更好地近似。还知道，即使C均匀并且D^*是常数，问题也很难NP。这项研究的结果表明，如果d^*是常数，则如果C均匀，则可能近似常数。它还表明即使D^*是常数，APX也很困难。

项目成果

A robust algorithm for bisecting a triconnected graph with two resource sets

• DOI: 10.1016/j.tcs.2005.06.010
• 发表时间: 2005-09
• 期刊: Theor. Comput. Sci.
• 作者: H. Nagamochi;K. Iwata;Toshimasa Ishii

Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs

无向图中具有单调要求的边连通性的最小增强

• 发表时间: 2007
• 期刊: Proceedings of the 13th Computing Theory : The Australian Theory Symposium
• 作者: Toshimasa Ishii;Hitoshi Fujita;Hiroshi Nagamochi;Toshimasa Ishii
• 通讯作者: Toshimasa Ishii

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

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

• 发表时间: 2006
• 期刊: Algorithmica Vo. 44,no. 3
• 作者: Toshimasa Ishii;Hiroshi Nagamochi;Toshihide Ibaraki
• 通讯作者: Toshihide Ibaraki

Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs

无向图中顶点和顶点子集之间的局部边连通性的最小增强

• 期刊: Discrete Applied Mathematics vol.154, issue 16
• 作者: Toshimasa Ishii;Masayuki Hagiwara
• 通讯作者: Masayuki Hagiwara

Bisecting a four-connected graph with three resource sets

用三个资源集平分四连通图

• 期刊: Discrete Applied Mathematics (掲載確定)
• 作者: S.;Imahori;T. Hasunuma;H.Nagamochi;E. Morsy;H.Nagamochi;Y. Kamidoi;H. Nagamochi;H. Nagamochi;H. Nagamochi;H. Nagamochi;T.Ishii;H.Nagamochi;Y.Kamidoi;H.Nagamochi;H.Nagamochi;H.Nagamochi;P.Eades;T.Ishii;H.Nagamochi;H. Nagamochi;H. Nagamochi;H.Nagamochi;L.Zhao;H.Nagamochi;H.Nagamochi;H.Nagamochi;H.Nagamochi;石井利昌;H.Nagamochi;H.Nagamochi;H.Nagamochi;Y.Karuno;Y.Kamidoi;H.Nagamochi;H.Nagamochi;T.Ishii
• 通讯作者: T.Ishii