{"created":"2023-07-25T10:25:33.024638+00:00","id":3932,"links":{},"metadata":{"_buckets":{"deposit":"96ab0cbd-7ce8-4a50-8482-e053be551f43"},"_deposit":{"created_by":4,"id":"3932","owners":[4],"pid":{"revision_id":0,"type":"depid","value":"3932"},"status":"published"},"_oai":{"id":"oai:naist.repo.nii.ac.jp:00003932","sets":["34:35"]},"author_link":["7042","7043","36","7044","7045"],"item_7_biblio_info_9":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2015-09-25","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"11","bibliographicPageStart":"1","bibliographicVolumeNumber":"617","bibliographic_titles":[{"bibliographic_title":"Theoretical Computer Science","bibliographic_titleLang":"en"}]}]},"item_7_description_7":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"In this paper, we consider the partial gathering problem of mobile agents in asynchronous unidirectional rings equipped with whiteboards on nodes. The partial gathering problem is a new generalization of the total gathering problem. The partial gathering problem requires, for a given integer g, that each agent should move to a node and terminate so that at least g   agents should meet at the same node. The requirement for the partial gathering problem is weaker than that for the (well-investigated) total gathering problem, and thus, we have interests in clarifying the difference on the move complexity between them. We propose three algorithms to solve the partial gathering problem. The first algorithm is deterministic but requires unique ID of each agent. This algorithm achieves the partial gathering in O(gn)O(gn) total moves, where n   is the number of nodes. The second algorithm is randomized and requires no unique ID of each agent (i.e., anonymous). This algorithm achieves the partial gathering in expected O(gn)O(gn) total moves. The third algorithm is deterministic and requires no unique ID of each agent. For this case, we show that there exist initial configurations in which no algorithm can solve the problem and agents can achieve the partial gathering in O(kn)O(kn) total moves for solvable initial configurations, where k   is the number of agents. Note that the total gathering problem requires Ω(kn)Ω(kn) total moves, while the partial gathering problem requires Ω(gn)Ω(gn) total moves in each model. Hence, we show that the move complexity of the first and second algorithms is asymptotically optimal.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_7_publisher_10":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Elsevier","subitem_publisher_language":"en"}]},"item_7_relation_17":{"attribute_name":"出版者版DOI","attribute_value_mlt":[{"subitem_relation_type":"isIdenticalTo","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1016/j.tcs.2015.09.012","subitem_relation_type_select":"DOI"}}]},"item_7_rights_18":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"出版社許諾条件により本文は2017/09/25以降に公表。","subitem_rights_language":"ja"},{"subitem_rights":"Copyright c 2015 The Authors","subitem_rights_language":"en"}]},"item_7_source_id_12":{"attribute_name":"EISSN/PISSN","attribute_value_mlt":[{"subitem_source_identifier":"0304-3975","subitem_source_identifier_type":"ISSN"}]},"item_7_source_id_14":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA00862688","subitem_source_identifier_type":"NCID"}]},"item_7_version_type_20":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_access_right":{"attribute_name":"アクセス権","attribute_value_mlt":[{"subitem_access_right":"open access","subitem_access_right_uri":"http://purl.org/coar/access_right/c_abf2"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Shibata, Masahiro","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"7042","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Kawai, Shinji","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"7043","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Ooshita, Fukuhito","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"36","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"20362650","nameIdentifierScheme":"e-Rad","nameIdentifierURI":"https://kaken.nii.ac.jp/ja/search/?qm=20362650"}]},{"creatorNames":[{"creatorName":"Kakugawa, Hirotsugu","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"7044","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Masuzawa, Toshimitsu","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"7045","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2023-03-02"}],"displaytype":"detail","filename":"1-s2.0-S0304397515008270-main.pdf","filesize":[{"value":"456.3 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"fulltext","objectType":"fulltext","url":"https://naist.repo.nii.ac.jp/record/3932/files/1-s2.0-S0304397515008270-main.pdf"},"version_id":"3e21e48a-5c11-4abd-a163-d3b6ca643393"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"Distributed system","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Mobile agent","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Gathering problem","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Partial gathering","subitem_subject_language":"en","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":"Partial gathering of mobile agents in asynchronous unidirectional rings","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Partial gathering of mobile agents in asynchronous unidirectional rings","subitem_title_language":"en"}]},"item_type_id":"7","owner":"4","path":["35"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2017-09-25"},"publish_date":"2017-09-25","publish_status":"0","recid":"3932","relation_version_is_last":true,"title":["Partial gathering of mobile agents in asynchronous unidirectional rings"],"weko_creator_id":"4","weko_shared_id":-1},"updated":"2023-11-29T08:31:55.214087+00:00"}