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

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

• 批准号: 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困難であることも示した.

Communication network, network, VLSI の wiring, facilities configuration problems な ど now be social に お い て solve が o め ら れ る more く が の problem, グ ラ フ · ネ ッ ト ワ ー ク tectonic を hold つ せ combination optimization problem と し て demean さ れ る. グ ラ フ theory に お け る link degree の は, kind of 々 の ネ ッ ト ワ ー ク の system royal · design に お い て, resistance to it Obstacle に is related to する. The basic な evaluation 価 criteria と て て use に られる. This study で は, に link degree restricted を hold つ ネ ッ ト ワ ー ク design problem に を center, そ れ ら を solution く sharper rate な ア ル ゴ リ ズ ム を build す る こ と を purpose と す る. This year は こ れ ま が で applicants join わ っ て き た, 辺 の plus に よ り and え ら れ た link degree requirements を against た す よ う に グ ラ フ を raised large さ せ る link degree raised big questions や, link degree requirements を against た す よ う に nodes に な special facilities (supply) の collection を configuration す る supply point configuration problems に す seaborne る sharper rate な ア ル ゴ リ ズ ム の research Youdaoplaceholder0 is pushed to め, and the result is を to た. Example え ば, point link degree requirements for を つ supply point configuration problems の approximate probability に masato し て times の を た. Results, undirected グ ラ フ G = (V, E), masato number c: V - > R ^ +, masato number d: V - Z ^ + が and え ら れ た と き, between each node V ∈ V と S の に outside の node V を mutual し な い パ ス が し d (V) above, Σ _ < V ∈ > vc (V) が minimum で あ る node set S を o め る problem に し seaborne, c が a others の occasions, Max {d ^ *, The 2d^*-6} times approximation may である ただ とを とを prove that <s:1> た. Youdaoplaceholder3 ただ,d^*=max{d(v)] V ∈ v} で あ る. こ の は, こ れ ま で, P = NP で な い limit り, あ る constant c に し seaborne て herculean task (Σ _ < v ∈ > vd (v)) times よ い り good approximation が で き な い こ と が know ら れ て い る. ま た, c が a others か つ, d ^ * が destiny の と き で さ え, problem は NP difficult で あ る こ と が know ら れ て い る. This study achievements of の に よ り, d ^ * が destiny は の situations, c が a others で あ れ ば approximate number x で あ る こ と を shown し た. ま た, d ^ * が destiny の occasions で も APX difficult で あ る こ と も shown し た.

项目成果

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

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

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