{"created":"2023-05-15T11:55:21.927189+00:00","id":260,"links":{},"metadata":{"_buckets":{"deposit":"81d68ae6-beef-45cb-9637-d02479b84c58"},"_deposit":{"created_by":3,"id":"260","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"260"},"status":"published"},"_oai":{"id":"oai:kyutech.repo.nii.ac.jp:00000260","sets":["8:24"]},"author_link":["1127","1303"],"item_21_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2006-03","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicPageEnd":"51","bibliographicPageStart":"39","bibliographicVolumeNumber":"16","bibliographic_titles":[{"bibliographic_title":"Parallel Processing Letters (PPL)"}]}]},"item_21_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"In this paper, we consider a parallel algorithm for the patience sorting. The problem is not known to be in the class NC or P-complete. We propose two algorithms for the patience sorting of n distinct integers. The first algorithm runs in O(m(n/p+log n))time using p processors on the EREW PRAM, where m is the number of decreasing subsequences in a solution of the patience sorting. The second algorithm runs in O(log n+n log n/p+m2log n/p+m log p)time using p processors on the EREW PRAM. If 1<p<n/m2 is satisfied, the second algorithm becomes cost optimal.","subitem_description_type":"Abstract"}]},"item_21_description_60":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"subitem_description":"Journal Article","subitem_description_type":"Other"}]},"item_21_full_name_3":{"attribute_name":"著者別名","attribute_value_mlt":[{"affiliations":[{"affiliationNames":[{"affiliationName":"","lang":"ja"}],"nameIdentifiers":[]}],"familyNames":[{"familyName":"Fujiwara","familyNameLang":"en"},{"familyName":"藤原","familyNameLang":"ja"},{"familyName":"フジワラ","familyNameLang":"ja-Kana"}],"givenNames":[{"givenName":"Akihiro","givenNameLang":"en"},{"givenName":"暁宏","givenNameLang":"ja"},{"givenName":"アキヒロ","givenNameLang":"ja-Kana"}],"nameIdentifiers":[{"nameIdentifier":"1127","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"10295008","nameIdentifierScheme":"e-Rad","nameIdentifierURI":"https://nrid.nii.ac.jp/ja/nrid/1000010295008"},{"nameIdentifier":"7202215463","nameIdentifierScheme":"Scopus著者ID","nameIdentifierURI":"https://www.scopus.com/authid/detail.uri?authorId=7202215463"},{"nameIdentifier":"213","nameIdentifierScheme":"九工大研究者情報","nameIdentifierURI":"https://hyokadb02.jimu.kyutech.ac.jp/html/213_ja.html"}],"names":[{"name":"Fujiwara, Akihiro","nameLang":"en"},{"name":"藤原, 暁宏","nameLang":"ja"},{"name":"フジワラ, アキヒロ","nameLang":"ja-Kana"}]}]},"item_21_publisher_7":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"World Scientific Publishing Company"}]},"item_21_relation_12":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1142/S0129626406002459","subitem_relation_type_select":"DOI"}}]},"item_21_relation_14":{"attribute_name":"情報源","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"http://www.worldscinet.com/ppl/ppl.shtml"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"http://www.worldscinet.com/ppl/ppl.shtml","subitem_relation_type_select":"URI"}}]},"item_21_rights_13":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright © World Scientific Publishing Company"}]},"item_21_select_59":{"attribute_name":"査読の有無","attribute_value_mlt":[{"subitem_select_item":"yes"}]},"item_21_source_id_8":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0129-6264","subitem_source_identifier_type":"ISSN"}]},"item_21_text_36":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Tottori University of Environmental Studies, Wakabadai-Kita 1-1-1, Tottori, Tottori, 689-1111, Japan"},{"subitem_text_value":"Department of Computer Science and Electronics, Kyushu Institute of Technology, Kawazu 680-4, Iizuka, Fukuoka, 820-8502, Japan"}]},"item_21_version_type_58":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_ab4af688f83e57aa","subitem_version_type":"AM"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Nakashima, Takaaki"}],"nameIdentifiers":[{}]},{"creatorAffiliations":[{"affiliationNameIdentifiers":[],"affiliationNames":[{"affiliationName":""}]}],"creatorNames":[{"creatorName":"Fujiwara, Akihiro","creatorNameLang":"en"},{"creatorName":"藤原, 暁宏","creatorNameLang":"ja"},{"creatorName":"フジワラ, アキヒロ","creatorNameLang":"ja-Kana"}],"familyNames":[{},{},{}],"givenNames":[{},{},{}],"nameIdentifiers":[{},{},{},{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2007-12-18"}],"displaytype":"detail","filename":"S0129626406002459.pdf","filesize":[{"value":"258.3 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"S0129626406002459.pdf","url":"https://kyutech.repo.nii.ac.jp/record/260/files/S0129626406002459.pdf"},"version_id":"aa4059ac-967f-42ab-a25a-348652c54621"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"Patience sorting","subitem_subject_scheme":"Other"},{"subitem_subject":"parallel algorithms","subitem_subject_scheme":"Other"},{"subitem_subject":"P-completeness","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":"A Cost Optimal Parallel Algorithm for Patience Sorting","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"A Cost Optimal Parallel Algorithm for Patience Sorting"}]},"item_type_id":"21","owner":"3","path":["24"],"pubdate":{"attribute_name":"公開日","attribute_value":"2007-12-18"},"publish_date":"2007-12-18","publish_status":"0","recid":"260","relation_version_is_last":true,"title":["A Cost Optimal Parallel Algorithm for Patience Sorting"],"weko_creator_id":"3","weko_shared_id":3},"updated":"2023-10-25T08:51:06.080246+00:00"}