WEKO3
インデックスリンク
アイテム
Small congestion embedding of graphs into hypercubes
http://hdl.handle.net/2297/3642
http://hdl.handle.net/2297/364230d103cb-5b4b-4424-a82c-18620f245df6
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
TE-PR-MATSUBAYASI-A-71.pdf (117.6 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2017-10-03 | |||||
| タイトル | ||||||
| タイトル | Small congestion embedding of graphs into hypercubes | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 著者 |
Matsubayashi, Akira
× Matsubayashi, Akira× Ueno, Shuichi |
|||||
| 提供者所属 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 金沢大学大学院自然科学研究科知能情報・数理 | |||||
| 提供者所属 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 金沢大学工学部 | |||||
| 書誌情報 |
Networks 巻 33, 号 1, p. 71-77, 発行日 1999-01-15 |
|||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 0028-3045 | |||||
| DOI | ||||||
| 関連タイプ | isVersionOf | |||||
| 識別子タイプ | DOI | |||||
| 関連識別子 | https://doi.org/10.1002/(sici)1097-0037(199901)33:1<71::aid-net5>3.0.co;2-3 | |||||
| 出版者 | ||||||
| 出版者 | John Wiley & Sons | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | We consider the problem of embedding graphs into hypercubes with minimal congestion. Kim and Lai showed that for a given N-vertex graph G and a hypercube it is NP-complete to determine whether G is embeddable in the hypercube with unit congestion, but G can be embedded with unit congestion in a hypercube of dimension 6[log N] if the maximum degree of a vertex in G is no more than 6[log N]. Bhatt et al. showed that every N-vertex binary tree can be embedded in a hypercube of dimension [log N] with O(1) congestion. In this paper, we extend the results above and show the following : (1) Every N-vertex graph G can be embedded with unit congestion in a hypercube of dimension 2[log N] if the maximum degree of a vertex in G is no more than 2[log N], and (2) every N-vertex binary tree can be embedded in a hypercube of dimension [log N] with congestion at most 5. The former answers a question posed by Kim and Lai. The latter is the first result that shows a simple embedding of a binary tree into an optimal-sized hypercube with an explicit small congestion of 5. This partially answers a question posed by Bhatt et al. The embeddings proposed here are quite simple and can be constructed in polynomial time. © 1999 John Wiley & Sons, Inc. Networks 33: 71-77, 1999. | |||||
| 著者版フラグ | ||||||
| 出版タイプ | AM | |||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
