著者

トム アルトマン 五十嵐 善英 小保方 幸次

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.93, no.123, pp.9-18, 1993-06-25

---

グラフG=(V,E)が,V={0,…,N-1},E={{u,v}|v-u modulo Nが2の冪乗}であるときこのグラフを頂点数Nのハイパーリング(N-HR)という。本稿では,HRの構成法,特性,埋め込み,スパナについて論じる。頂点数Nのハイパーキューブや,a×b格子,頂点数Nの完全二分木を,N-HRに部分グラフとして埋め込む.また,HRのスパナの構成方法を3タイプ紹介する.これらのタイプのスパナの伸び率は,HRの頂点数をNとすると高々[log_2N],任意の1【less than or equal】k【less than or equal】[log_2N]に対し2k-1,任意の2【less than or equal】k【less than or equal】[log_2N]-1に対し2k-1である.また,これらのタイプのスパナを構成する辺の数は,N-1,高々N[log_2N), k],高々N(log_2N-k)/2k+Nkである.最後に,HRのγシンクロナイザに関する伸び率と辺の数の表を示す.