WEKO3
-
RootNode
アイテム
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
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
|
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 (情報処理学会) |