权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
17700011
负责人：
石井利昌
金额：
$ 2.18万
依托单位：
Otaru University of Commerce (2006-2007)Toyohashi University of Technology (2005)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2005
资助国家：
日本
起止时间：
2005 至 2007
项目状态：
已结题

项目摘要

通信網・交通網,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, transportation network,VLSI wiring, configuration problems, social problems, optimization problems, etc. The concept of connectivity in theory is a basic evaluation criterion for the design, control and fault tolerance of a variety of products. This study is aimed at solving the problem of connectivity constraints, which are central to the design process. This year, the applicant has been carrying out research on the increase in connectivity and the increase in connectivity requirements, and the increase in connectivity has been achieved. For example, the link degree requirement is maintained and the approximate probability of the supply point configuration problem is obtained.·G=(V, E), relation c: V→R^+, relation d: V→Z^+, all nodes v∈V → S have nodes other than v in common, so there exists a minimum set of nodes S. In this case,max{d^*, 2d^*-6} times the approximate probability is proved.ただし,d^*=max{d(v) | v∈V}である. The problem is: P=NPまた,cが一様かつ,d^*が定数のときでさえ,问题はNP困难であることが知られている. The results of this study show that d^* is a fixed number of times,c is a fixed number of times, and c is a fixed number of times. D^* is a fixed number of cases.

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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.
影响因子：
0
作者：
H. Nagamochi;K. Iwata;Toshimasa Ishii
通讯作者：
H. Nagamochi;K. Iwata;Toshimasa Ishii

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

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

DOI：
发表时间：
2007
期刊：
Proceedings of the 13th Computing Theory : The Australian Theory Symposium
影响因子：
0
作者：
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 顶点连接的多重图

DOI：
发表时间：
2006
期刊：
Algorithmica Vo. 44,no. 3
影响因子：
0
作者：
Toshimasa Ishii;Hiroshi Nagamochi;Toshihide Ibaraki
通讯作者：
Toshihide Ibaraki

Bisecting a four-connected graph with three resource sets

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

DOI：
发表时间：
期刊：
Discrete Applied Mathematics (掲載確定)
影响因子：
0
作者：
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

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