{"created":"2023-05-15T12:35:23.425276+00:00","id":295,"links":{},"metadata":{"_buckets":{"deposit":"9805dff8-fb1a-466b-85bb-e242b1017b98"},"_deposit":{"created_by":2,"id":"295","owners":[2],"pid":{"revision_id":0,"type":"depid","value":"295"},"status":"published"},"_oai":{"id":"oai:kutarr.kochi-tech.ac.jp:00000295","sets":["5"]},"author_link":["1322","1323"],"item_2_biblio_info_7":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2014-12","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicPageEnd":"9","bibliographicPageStart":"1","bibliographicVolumeNumber":"7","bibliographic_titles":[{"bibliographic_title":"IPSJ Transaction on Programming"}]}]},"item_2_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Abstract"}]},"item_2_publisher_35":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Information Processing Society of Japan (情報処理学会)"}]},"item_2_rights_14":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright © 2014 by the Information Processing Society of Japan"}]},"item_2_source_id_9":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7802","subitem_source_identifier_type":"ISSN"}]},"item_2_version_type_18":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Morihata, Akimasa"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Matsuzaki, Kiminori"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2019-02-13"}],"displaytype":"detail","filename":"28-57.pdf","filesize":[{"value":"372.4 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"28-57.pdf","url":"https://kutarr.kochi-tech.ac.jp/record/295/files/28-57.pdf"},"version_id":"8f18821e-b295-44ae-93e5-33c30efab51d"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"parallel tree contraction","subitem_subject_scheme":"Other"},{"subitem_subject":"rose tree","subitem_subject_scheme":"Other"},{"subitem_subject":"m-bridge decomposition","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree"}]},"item_type_id":"2","owner":"2","path":["5"],"pubdate":{"attribute_name":"公開日","attribute_value":"2017-03-24"},"publish_date":"2017-03-24","publish_status":"0","recid":"295","relation_version_is_last":true,"title":["Parallel Tree Contraction with Fewer Types of Primitive Contraction Operations and Its Application to Trees of Unbounded Degree"],"weko_creator_id":"2","weko_shared_id":-1},"updated":"2023-05-15T13:39:03.117496+00:00"}