WEKO3
アイテム
{"_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": ["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\u003cp\u003cn/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": [{"nameIdentifier": "1303", "nameIdentifierScheme": "WEKO"}]}, {"creatorAffiliations": [{"affiliationNameIdentifiers": [], "affiliationNames": [{"affiliationName": "", "affiliationNameLang": "ja"}]}], "creatorNames": [{"creatorName": "Fujiwara, Akihiro", "creatorNameLang": "en"}, {"creatorName": "藤原, 暁宏", "creatorNameLang": "ja"}, {"creatorName": "フジワラ, アキヒロ", "creatorNameLang": "ja-Kana"}], "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"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2007-12-18"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "S0129626406002459.pdf", "filesize": [{"value": "258.3 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 258300.0, "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"], "permalink_uri": "http://hdl.handle.net/10228/530", "pubdate": {"attribute_name": "公開日", "attribute_value": "2007-12-18"}, "publish_date": "2007-12-18", "publish_status": "0", "recid": "260", "relation": {}, "relation_version_is_last": true, "title": ["A Cost Optimal Parallel Algorithm for Patience Sorting"], "weko_shared_id": 3}
A Cost Optimal Parallel Algorithm for Patience Sorting
http://hdl.handle.net/10228/530
http://hdl.handle.net/10228/530a3b49363-d4ba-4d7b-932e-8edf739c5a26
名前 / ファイル | ライセンス | アクション |
---|---|---|
S0129626406002459.pdf (258.3 kB)
|
|
Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2007-12-18 | |||||||||||
資源タイプ | ||||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
資源タイプ | journal article | |||||||||||
タイトル | ||||||||||||
タイトル | A Cost Optimal Parallel Algorithm for Patience Sorting | |||||||||||
言語 | ||||||||||||
言語 | eng | |||||||||||
著者 |
Nakashima, Takaaki
× Nakashima, Takaaki× 藤原, 暁宏
WEKO
1127
|
|||||||||||
抄録 | ||||||||||||
内容記述タイプ | Abstract | |||||||||||
内容記述 | 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. | |||||||||||
書誌情報 |
Parallel Processing Letters (PPL) 巻 16, 号 1, p. 39-51, 発行日 2006-03 |
|||||||||||
出版社 | ||||||||||||
出版者 | World Scientific Publishing Company | |||||||||||
DOI | ||||||||||||
関連タイプ | isVersionOf | |||||||||||
識別子タイプ | DOI | |||||||||||
関連識別子 | https://doi.org/10.1142/S0129626406002459 | |||||||||||
ISSN | ||||||||||||
収録物識別子タイプ | ISSN | |||||||||||
収録物識別子 | 0129-6264 | |||||||||||
著作権関連情報 | ||||||||||||
権利情報 | Copyright © World Scientific Publishing Company | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | Patience sorting | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | parallel algorithms | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | P-completeness | |||||||||||
出版タイプ | ||||||||||||
出版タイプ | AM | |||||||||||
出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||
査読の有無 | ||||||||||||
値 | yes | |||||||||||
著者別名 | ||||||||||||
姓名 | Fujiwara, Akihiro | |||||||||||
言語 | en | |||||||||||
姓名 | 藤原, 暁宏 | |||||||||||
言語 | ja | |||||||||||
姓名 | フジワラ, アキヒロ | |||||||||||
言語 | ja-Kana | |||||||||||
情報源 | ||||||||||||
識別子タイプ | URI | |||||||||||
関連識別子 | http://www.worldscinet.com/ppl/ppl.shtml | |||||||||||
関連名称 | http://www.worldscinet.com/ppl/ppl.shtml |