ハイパーキューブの耐故障グラフ

書誌事項

タイトル別名
  • Falt-Tolerant Graphs for Hypercubes

この論文をさがす

説明

与えられたn点から成るグラフHに対して,n点から成るグラフGから任意のt本の辺を除去しても,残りのグラフにHが部分グラフとして含まれているとき,GをHのt-耐故障グラフという.Hのt-耐故障グラフGに関する|E(G)|-|E(H)|の最小値を△(t,H)で表す.n次元キューブQ(n)に対して,△(1,Q(n))=2^n-1>であることが知られている.小文では,これを自然に一般化して,△(t,Q(n))=O(t2^n-1>logn)(2【less than or equal】tnln2)であることを示す.これは,誤り訂正線形符号を用いてQ(n)のt-耐故障グラフを構成することによって示される.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1571698602306589696
  • NII論文ID
    110003198233
  • NII書誌ID
    AN10013094
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ