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家族，故障诊断和图形产物的图。1。 De Bruijn家族的图：通过循环生根的树对De Bruijn图的分解，确定色数和色度指数，确定广义de Bruijn图的支配数，广播算法的建议。2。故障诊断：通过比较方法，最佳诊断和通过自适应故障诊断，（T，K）故障诊断及其表征的建议，通过比较方法，最佳诊断和对蝴蝶网络对蝴蝶网络的持续圆形分析，对Cayley图上的网络进行最佳诊断的必要条件，对蝴蝶网络上的故障诊断算法的建议。3。图形的产物：针对小组花圈产品的新图的建议。

项目成果

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: "Efficient Diagnosis Algorithm on Butterfly Networks under the Comparison Approach"IEICE Trans. Fundamentals 発表予定. E85-A・4. (2002)

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

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

T. Araki：“(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。

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

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