| 講演名 | 2003/10/20 最適なマージングネットワークについて 天野 一幸, 丸岡 章, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | Batcherのodd-even法によって生成される(m, n)-マージングネットワークが(m, n)=(3,4k+2)と(4,4k+2)の場合に,比較交換器数において真に最適であることを証明する.m≦4に限定した場合,これ以外の入力要素数に対しては既に最適性が示されているので,この結果は,任意の1≦m≦4,1≦nに愛するodd-even法の最適性を結論付けるものである. |
| 抄録(英) | We prove that Batcher's odd-even (m, n)-merging networks are exactly optimal for (m, n)=(3,4k+2) and (4,4k+2) for k≧0 in terms of the number of comparators used. For other cases where m≦4, the optimality of Batcher's (m, n)-merging networks has been proved. So we can conclude that Batcher's odd-even merge yields optimal (m, n)-merging networks for every m≦4 and for every n. |
| キーワード(和) | 比較器回路網 / マージングネットワーク / Batcherのodd-even法 / 下界 |
| キーワード(英) | comparator networks / merging networks / Batcher's odd-even merge / lower bounds |
| 資料番号 | COMP2003-53 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2003/10/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 最適なマージングネットワークについて |
| サブタイトル（和） | |
| タイトル（英） | On Optimal Merging Networks |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 比較器回路網 / comparator networks |
| キーワード(2)（和/英） | マージングネットワーク / merging networks |
| キーワード(3)（和/英） | Batcherのodd-even法 / Batcher's odd-even merge |
| キーワード(4)（和/英） | 下界 / lower bounds |
| 第 1 著者 氏名（和/英） | 天野 一幸 / Kazuyuki AMANO |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 GSIS, Tohoku University |
| 第 2 著者 氏名（和/英） | 丸岡 章 / Akira MARUOKA |
| 第 2 著者 所属（和/英） | 東北大学大学院情報科学研究科 GSIS, Tohoku Univeristy |
| 発表年月日 | 2003/10/20 |
| 資料番号 | COMP2003-53 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 394 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |