Butterfly networksのde Bruijn network及びKautz networkへの埋め込みについて

• Item type: SIG Technical Reports(1)
• 公開日: 1994-09-21
• タイトル: Butterfly networksのde Bruijn network及びKautz networkへの埋め込みについて
• タイトル / 言語: en
• タイトル: Embedding butterflies in de Bruijn and Kautz networks
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Gunma University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Gunma University
• 著者名: 蓮沼, 徹; 柴田, 幸夫
• 著者名(英): Toru, Hasunuma; Yukio, Shibata
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: butterfly networksのde Bruijn network及びKautz networkへの部分グラフとしての埋め込みについて考察する。r?dimensional k?aryのbutterfly network、de Bruijn graph、Kautz graphをそれぞれb（，），UB（，），UK（，）で表すとする。UB（，）(（，））がb（，D?），i=1，2，．．．，d?1を頂点を共有しない形で含むことが示される。又、UB（，）(（，））がkP（?1，〓d/k〓?）+〓d/k〓^<D?1>（ mod ）個のb（，D?）に同型な部分グラフを頂点を共有しない形で含むことも示される。ここで、P（，）=Σ_<1〓i〓n^i^r>であり、実数xに対して、〓x〓はxを越えない最大の整数を表す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We investigate the embeddability of the butterflies in the de Bruijn and Kautz networks. Suppose b(k,r), UB(k,r) and UK(k,r) denote the r-dimensional k-ary butterfly, de Bruijn graph and Kautz graph, respectively. Then it is proved that UB(d,D)(UK(d,D)) contains b(i,D-1), i=1,2,...,d-1 in vertex-disjoint manner. Also it is shown that UB(d,D)(UK(d,D)) contains kP(D-1,〓d/k〓-1)+〓d/k〓^<D-1>(d mod k) vertex-disjoint copies of b(k,D-1), where P(r,n)=Σ_<1〓i〓n^i^r> and 〓x〓 stands for the greatest integer not exceeding a real number x.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1994, 号 82(1994-AL-041), p. 65-72, 発行日 1994-09-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会