| 講演名 | 2000/4/26 ハイパーキューブとパスの積グラフの分解について 菊地 洋右, 尾高 博之, 柴田 幸夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | グラフの斜積はY.Shibata and Y.Kikuchi, Graph products based on the distance in graphs, IEICE Trans.Fundamentals, E83-A, 3(2000)459-464において定義された。この斜積を奇数次元のハイパーキューブとその次元よりも1長いパスに施し新しいグラフを構成した。この構成されたグラフがバタフライで同型因子分解されることを示す。この同型因子分解されることの証明に際してswallowtailグラフとtwisted swallowtailグラフを導入する。さらに、偶数次元のハイパーキューブとその次元よりも1長いパスの斜積の場合はバタフライでは同型因子分解できないが、バタフライとパスによる分解が可能であることを示す。 |
| 抄録(英) | The skew product of graphs is introduced in Y.Shibata and Y.Kikuchi, Graph products based on the distance in graphs, IEICE Trans. Fundamentals, E83-A, 3(2000) 459-464. We introduce a new class of graphs using the skew product. This class is the skew product of a hypercube and a path, where the length of the path is greater than the dimension of the hypercube by one. We show that if n is odd, then the skew product of the n dimensional hypercube and the path of length n+1 is isomorphically factorized by the n-dimensional butterfly. We introduce the swallowtail graph and the twisted swallowtail graph that play an important role in the proof of the above statement. Moreover, we show that if n is even, then the skew product of the n dimensional hypercube and the path of length n+1 is decomposed by n/2 n-dimensional butterflies and 2^n paths of length n+1. |
| キーワード(和) | ハイパーキューブ / バタフライ / 斜積 / 同型因子分解 |
| キーワード(英) | hypercube / butterfly / skew product / isomorphic factorization |
| 資料番号 | COMP2000-2 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/4/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ハイパーキューブとパスの積グラフの分解について |
| サブタイトル（和） | |
| タイトル（英） | On the factorization of the product graph of a hypercube and a path |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ハイパーキューブ / hypercube |
| キーワード(2)（和/英） | バタフライ / butterfly |
| キーワード(3)（和/英） | 斜積 / skew product |
| キーワード(4)（和/英） | 同型因子分解 / isomorphic factorization |
| 第 1 著者 氏名（和/英） | 菊地 洋右 / Yosuke Kikuchi |
| 第 1 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Gunma University |
| 第 2 著者 氏名（和/英） | 尾高 博之 / Hiroyuki Odaka |
| 第 2 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Gunma University |
| 第 3 著者 氏名（和/英） | 柴田 幸夫 / Yukio Shibata |
| 第 3 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science, Gunma University |
| 発表年月日 | 2000/4/26 |
| 資料番号 | COMP2000-2 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 25 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |