| 講演名 | 2002/11/1 点平衡木の最適点数格子への定数辺負荷埋め込み 松林 昭, 中村 裕之, 宮道 壽一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | メッセージ交換並列計算機に並列アルゴリズムを効率的に実装する問題や,ネットワークを他のネットワークで効率的にシミュレートする問題は,グラフ埋め込み問題として定式化され,長年に渡って研究されている。特に,メッセージ交換方式として回路交換を採用したシステムにおいては,小さい辺負荷の埋め込みを構成することが重要であることが知られている.小文では,各々の点uに対して,uの子を根とする部分木の点数の比が高々定数であるような任意の2分木は,同じ点数の格子に定数辺負荷で埋め込めることを示す. |
| 抄録(英) | The problem of efficiently implementing parallel algorithms on message passing parallel computer systems and the problem of efficiently simulating networks by other networks have been studied for many years as the graph embedding problem. In particular it is known that the minimal congestion embedding is very important for a parallel system which adopts cut-through switching techniques, which are well used in recent architectures for node-to-node communication. In this paper, we show that every binary tree such that for each vertex u, the ratio of the number of vertices of the subtrees rooted by children of u is bounded by a constant can be embedded with constant congestion into a grid with the same number of vertices as that of the tree. |
| キーワード(和) | グラフ埋め込み / 辺負荷 / 格子 / 平衡木 |
| キーワード(英) | graph embedding / congestion / grid / balanced tree |
| 資料番号 | CAS 2002-86 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CAS |
|---|---|
| 開催期間 | 2002/11/1(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Circuits and Systems (CAS) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 点平衡木の最適点数格子への定数辺負荷埋め込み |
| サブタイトル（和） | |
| タイトル（英） | Constant Congestion Embedding of Node Balanced Trees into Optimal-Sized Grids |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ埋め込み / graph embedding |
| キーワード(2)（和/英） | 辺負荷 / congestion |
| キーワード(3)（和/英） | 格子 / grid |
| キーワード(4)（和/英） | 平衡木 / balanced tree |
| 第 1 著者 氏名（和/英） | 松林 昭 / Akira MATSUBAYASHI |
| 第 1 著者 所属（和/英） | 金沢大学工学部 Faculty of Engineering, Kanazawa University |
| 第 2 著者 氏名（和/英） | 中村 裕之 / Hiroyuki NAKAMURA |
| 第 2 著者 所属（和/英） | 宇都宮大学工学部 Faculty of Engineering, Utsunoiniya University |
| 第 3 著者 氏名（和/英） | 宮道 壽一 / Juichi MIYAMICHI |
| 第 3 著者 所属（和/英） | 宇都宮大学工学部 Faculty of Engineering, Utsunoiniya University |
| 発表年月日 | 2002/11/1 |
| 資料番号 | CAS 2002-86 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 426 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |