Design of algorithms for problems of fault-tolerance of networks

网络容错问题的算法设计

• 批准号: 23500007
• 负责人: ARAKI Toru
• 金额: $ 2.75万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500007/
• 关键词: アルゴリズム; 情報基礎; グラフ理論; ネットワーク; 耐故障性; グラフアルゴリズム; 支配集合問題; 全域木; 完全独立全域木; 有向グラフ; 局所トーナメント; コーダルグラフ

In this study, we considered problems of domination in graphs, and the problem of completely independent spanning trees in graphs. It is known that these problems have been related to the problems of fault-tolerance in networks.First we considered the problems of domination in graphs, and we obtained some polynomial-time algorithms for problems of twin domination in round digraphs and local-tournaments which are well known classes of digraphs.Second, we considered the problem of completely independent spanning trees. This problem is a model of fault-tolerant routing in networks. We obtain some new sufficient condition of the existence of completely independent spanning trees in graphs.

在本研究中，我们考虑了图的控制问题和图的完全独立生成树问题。 我们首先研究了图的控制问题，得到了有向图的圈图和局部竞赛图的孪生控制问题的多项式时间算法，然后研究了图的完全独立生成树问题。 该问题是网络中的容错路由模型。得到了图中完全独立生成树存在的一些新的充分条件。

项目成果

Twin Domination Problems in Round Digraphs

• DOI: 10.1587/transfun.e97.a.1192
• 发表时间: 2014-06
• 期刊: IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
• 作者: T. Nakajima;Yuuki Tanaka;Toru Araki

ラウンドダイグラフの双方向支配集合

圆形有向图的双向支配集

• 发表时间: 2011
• 作者: 中島 環;荒木 徹
• 通讯作者: 荒木 徹

局所完全ダイグラフの独立双方向支配集合について

关于局部完全有向图的独立双向支配集

• 发表时间: 2012
• 作者: 山中克久;中野眞一;Toshihiro Shirakawa and Ryuhei Uehara;荒木 徹
• 通讯作者: 荒木 徹

Dirac's Condition for Completely Independent Spanning Trees

• DOI: 10.1002/jgt.21780
• 发表时间: 2014-11
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: Toru Araki

区間グラフの向き付けにおける双方向支配

区间图方向的双向优势

• 发表时间: 2012
• 作者: 原田 高浩;荒木 徹
• 通讯作者: 荒木 徹