WEKO3
アイテム
Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree
http://hdl.handle.net/10173/1479
http://hdl.handle.net/10173/14790475f7c1-e132-44a2-91f7-f98a91a1c5e3
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
28-57.pdf (372.4 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2017-03-24 | |||||||||
| タイトル | ||||||||||
| タイトル | Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | parallel tree contraction | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | rose tree | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | m-bridge decomposition | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| 著者 |
Morihata, Akimasa
× Morihata, Akimasa
× Matsuzaki, Kiminori
|
|||||||||
| 抄録 | ||||||||||
| 内容記述タイプ | Abstract | |||||||||
| 内容記述 | Parallel tree contraction is a well established method of parallel tree processing. There are efficient and useful algorithms for binary trees, including the Shunt contraction algorithm and one based on the m-bridge decomposition method. However, for trees of unbounded degree, there are few practical tree contraction algorithms. The standard approach is “binarization,” namely to translate the input tree to a full binary tree beforehand. To prevent the overhead introduced by binarization, we previously proposed the Rake-Shunt contraction algorithm (ICCS 2011), which is a generalization of the Shunt contraction algorithm to trees of unbounded degree. This paper further extends this result. The major contribution is to show that the Rake-Shunt contraction algorithm is a tree contraction algorithm that uses fewer types of primitive contraction operations if we assume the input tree has been binarized. This observation clarifies the connection between the Rake-Shunt contraction algorithm and those based on binarization. In particular, it enables us to translate a parallel program developed based on the Rake-Shunt contraction algorithm to one based on the m-bridge decomposition method. Thus, we can choose whether to use binarization according to the situation. | |||||||||
| 書誌情報 |
IPSJ Transaction on Programming 巻 7, 号 5, p. 1-9, 発行日 2014-12 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 1882-7802 | |||||||||
| 権利 | ||||||||||
| 権利情報 | Copyright © 2014 by the Information Processing Society of Japan | |||||||||
| 著者版フラグ | ||||||||||
| 出版タイプ | VoR | |||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||
| 出版者 | ||||||||||
| 出版者 | Information Processing Society of Japan (情報処理学会) | |||||||||
