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 (情報処理学会) | |||||
