Graph operation and its application to synthesis of interconnection networks and diagnosis of systems

图运算及其在互联网络综合和系统诊断中的应用

• 批准号: 13680392
• 负责人: SHIBATA Yukio
• 金额: $ 2.05万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680392/
• 关键词: interconnection network; fault diagnosis; de Bruijn graph; butterfly graph; Cayley graph; product of graphs; de Bruijn digraph; グラフの分解; ケーリーグラフ; バタフライネットワーク; recursive circulant graph

We studied on the synthesis and analysis of graphs for interconnection networks and fault diagnosis. We explain the results on graphs of de Bruijn family, fault diagnosis and product of graphs.1. Graph of de Bruijn family : decomposition of de Bruijn graphs by cycle rooted trees, determination of chromatic number and chromatic index, determination of domination number of generalized de Bruijn graphs, proposal of broadcasting algorithms.2. Fault diagnosis : necessary and sufficient condition for a network on Cayley graphs to be optimally diagnosable, proposal of fault diagnosis algorithm on butterfly networks by comparison approach, optimal diagnosis and constant round analysis of butterfly networks by adaptive fault diagnosis, proposal of (t,k) fault diagnosis and its characterization.3. Product of graphs : proposal of new graphs on Cayley graphs of wreath product of groups.

本文研究了用于互连网络和故障诊断的图的综合与分析。我们解释了de Bruijn族图、故障诊断和图的乘积的结果. de Bruijn图族：de Bruijn图的圈根树分解，色数和色指数的确定，广义de Bruijn图控制数的确定，广播算法的提出.故障诊断：Cayley图上网络可最优诊断的充要条件，蝶形网络故障诊断的比较法算法，蝶形网络自适应故障诊断的最优诊断和恒轮分析，（t，k）故障诊断的提出及其特征.图的积：群的圈积Cayley图的新图的提出。

项目成果

T.Araki: "(t, k)-Diagnosable Systems : a Generalization of the PMC Models"IEEE Trans. Computers. (発表予定).

T. Araki：“(t, k)-可诊断系统：PMC 模型的推广”IEEE Trans。

T.Araki and Y.Shibata: "(t,k)-Diagnosable System : a Generalization of the PMC Models"IEEE Trans. Computers, accepted.

T.Araki 和 Y.Shibata：“(t,k)-可诊断系统：PMC 模型的推广”IEEE Trans。

T.Araki: "(t,k)-Diagnosable Systems : a Generalization of the PMC Models"IEEE Trans. Computers. (発表予定).

T. Araki：“(t,k)-可诊断系统：PMC 模型的推广”IEEE Trans。

T.Araki: "Efficient Diagnosis Algorithm on Butterfly Networks under the Comparison Approach"IEICE Trans. Fundamentals 発表予定. E85-A・4. (2002)

T. Araki：“比较方法下的蝴蝶网络的高效诊断算法”IEICE Trans 基础知识（2002 年）。

Y.Kikuchi: "Broadcasting in Generalized de Bruijn Digraphs"Lecture Notes in Computer Science. 2387. 200-209 (2002)

Y.Kikuchi：“广义 de Bruijn 有向图的广播”计算机科学讲义。