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

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

基本信息

项目摘要

通信網・交通網,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
  • 期刊:
  • 影响因子:
    0
  • 作者:
    H. Nagamochi;K. Iwata;Toshimasa Ishii
  • 通讯作者:
    H. Nagamochi;K. Iwata;Toshimasa Ishii
Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs
无向图中具有单调要求的边连通性的最小增强
Augmenting a (k-1)-vertex-connected multigraph to an 1-edge-connected and k-vertex-connected multigraph
将 (k-1) 顶点连接的多重图增强为 1 边连接和 k 顶点连接的多重图
  • DOI:
  • 发表时间:
    2006
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Toshimasa Ishii;Hiroshi Nagamochi;Toshihide Ibaraki
  • 通讯作者:
    Toshihide Ibaraki
Bisecting a four-connected graph with three resource sets
用三个资源集平分四连通图
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    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
无向图中顶点和顶点子集之间的局部边连通性的最小增强
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

石井 利昌其他文献

石井 利昌的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('石井 利昌', 18)}}的其他基金

ネットワーク構造を有する離散最適化問題に対する高性能アルゴリズムとその応用
网络结构离散优化问题的高性能算法及其应用
  • 批准号:
    16K00001
  • 财政年份:
    2016
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
グラフの連結度増大問題に関する研究
图的连通性增强问题研究
  • 批准号:
    13780224
  • 财政年份:
    2001
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Young Scientists (B)

相似海外基金

終末期患者のQOL向上を目指した呼吸困難治療アルゴリズム作成に関する研究
创建旨在改善绝症患者生活质量的呼吸困难治疗算法的研究
  • 批准号:
    23K21406
  • 财政年份:
    2024
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
有用物質を効率的に生産する代謝ネットワークの設計アルゴリズム
设计有效产生有用物质的代谢网络的算法
  • 批准号:
    23K20386
  • 财政年份:
    2024
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
汎化指標デザインに基づく革新的学習アルゴリズムの探求と開発
基于广义指标设计的创新学习算法的探索与发展
  • 批准号:
    23K24902
  • 财政年份:
    2024
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
CT画像から解析したX線の入射方向情報を援用した患者表面線量分布の決定アルゴリズム
使用从 CT 图像分析的 X 射线入射方向信息确定患者表面剂量分布的算法
  • 批准号:
    24K21135
  • 财政年份:
    2024
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
機械学習アルゴリズムを用いた敗血症性凝固線溶障害の早期予測モデルの開発
使用机器学习算法开发脓毒性凝血和纤溶性疾病的早期预测模型
  • 批准号:
    24K12133
  • 财政年份:
    2024
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
アルゴリズムとアーキテクチャの協調によるベイジアンネットワークの学習推論基盤
基于算法与架构协同的贝叶斯网络学习与推理平台
  • 批准号:
    24KJ0578
  • 财政年份:
    2024
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
電子状態計算のための精度保証付き量子アルゴリズムの開拓
开发一种保证精确度的量子算法来计算电子态
  • 批准号:
    24K08334
  • 财政年份:
    2024
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
離散最適化問題に対する多様な解発見のためのアルゴリズム理論基盤の構築
为寻找离散优化问题的多种解决方案奠定算法理论基础
  • 批准号:
    23K28034
  • 财政年份:
    2024
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
高齢フレイルがん患者における身体機能評価アルゴリズムの開発
老年衰弱癌症患者身体机能评估算法的开发
  • 批准号:
    24K20552
  • 财政年份:
    2024
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
因果推論手法を用いた細胞療法の最適化アルゴリズムの開発
使用因果推理方法开发细胞治疗的优化算法
  • 批准号:
    24K19198
  • 财政年份:
    2024
  • 资助金额:
    $ 2.18万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了