Fault-Tolerant Hypercubes with Small Degree(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• For a given N-vertex graph H, a graph G obtained from H by adding t vertics and some edges is called a t-FT(t-fault-tolerant)graph for H if even after deleting any t vertics from G, the remaining graph contents H as a subgraph. For the n-dimensional cube Q(n) with N vectices, a t-FT graph with an optical number O(tN+t^2) of added edges and maximum dgree of O(N+t), and a t-FT graph with O(tNlogN) added edges and maximum degree of O(tlogN) have been known. In this paper, weintroduce some t-FT graphs for Q(n) with an optical number O(tN+t^2) of added edges and small maximum degree. In particular, we show a t-FT graph for Q(n) with 2ctN+ct^2(logN/c)^c added edges and maximum degree of O(n/log^<c/2>N)+4ct.

• 社団法人電子情報通信学会の論文
• 1998-05-25

著者

• Yamada Toshinori

  The Authors Are With The Department Of Physical Electronics Tokyo Institute Of Technology

• UENO Shuuichi

  The authors are with the Department of Physical Electronics, Tokyo Institute of Technology

• Ueno Shuuichi

  The Authors Are With The Department Of Physical Electronics Tokyo Institute Of Technology

関連論文

• Fault-Tolerant Hypercubes with Small Degree(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク