{"created":"2023-07-25T10:25:33.194445+00:00","id":3936,"links":{},"metadata":{"_buckets":{"deposit":"3b6a63d8-3141-4889-8b5c-166d8ecaefa7"},"_deposit":{"created_by":4,"id":"3936","owners":[4],"pid":{"revision_id":0,"type":"depid","value":"3936"},"status":"published"},"_oai":{"id":"oai:naist.repo.nii.ac.jp:00003936","sets":["34:35"]},"author_link":["7086","7087","7088","36","7089","7090"],"item_7_biblio_info_9":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2015-10-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"10","bibliographicPageEnd":"2128","bibliographicPageStart":"2117","bibliographicVolumeNumber":"E98-A","bibliographic_titles":[{"bibliographic_title":"IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences","bibliographic_titleLang":"en"}]}]},"item_7_description_7":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"We consider the exploration problem with a single agent in an undirected graph. The problem requires the agent starting from an arbitrary node to explore all the nodes and edges in the graph and return to the starting node. Our goal is to minimize both the number of agent moves and the memory size of the agent, which dominate the amount of communication during the exploration. We focus on the local memory called the whiteboard of each node. There are several exploration algorithms which are very fast (i.e. the exploration is completed within a small number of agent moves such as 2m and m+3n) and do not use whiteboards. These algorithms, however, require large agent memory because the agent must keep the entire information in its memory to explore a graph. We achieve the above goal by reducing the agent memory size of such algorithms with using whiteboards. Specifically, we present two algorithms with no agent memory based on the traditional depth-first traversal and two algorithms with O(n) and O(nlog n) space of agent memory respectively based on the fastest algorithms in the literature by Panaite and Pelc [J. Alg., Vol.33 No.2, 1999].","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_7_publisher_10":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"一般社団法人電子情報通信学会","subitem_publisher_language":"ja"}]},"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.1587/transfun.E98.A.2117","subitem_relation_type_select":"DOI"}}]},"item_7_rights_18":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright c 2015 IEICE","subitem_rights_language":"en"}]},"item_7_source_id_12":{"attribute_name":"EISSN/PISSN","attribute_value_mlt":[{"subitem_source_identifier":"1745-1337","subitem_source_identifier_type":"ISSN"}]},"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":"Sudo, Yuichi","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"7086","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Baba, Daisuke","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"7087","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Nakamura, Junya","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"7088","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":"7089","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Masuzawa, Toshimitsu","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"7090","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":"e98-a_10_2117.pdf","filesize":[{"value":"2.0 MB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"fulltext","objectType":"fulltext","url":"https://naist.repo.nii.ac.jp/record/3936/files/e98-a_10_2117.pdf"},"version_id":"c70ea968-baa7-44e7-84b7-64d2172ec224"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"graph exploration","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"mobile agent","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"whiteboard","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":"A Single Agent Exploration in Unknown Undirected Graphs with Whiteboards","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"A Single Agent Exploration in Unknown Undirected Graphs with Whiteboards","subitem_title_language":"en"}]},"item_type_id":"7","owner":"4","path":["35"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2016-11-22"},"publish_date":"2016-11-22","publish_status":"0","recid":"3936","relation_version_is_last":true,"title":["A Single Agent Exploration in Unknown Undirected Graphs with Whiteboards"],"weko_creator_id":"4","weko_shared_id":-1},"updated":"2023-11-29T08:31:59.483617+00:00"}