{"id":210984,"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00210984","sets":["1164:2592:10486:10582"]},"path":["10582"],"owner":"44499","recid":"210984","title":["最小数のエージェント群による動的グラフ探索"],"pubdate":{"attribute_name":"公開日","attribute_value":"2021-04-30"},"_buckets":{"deposit":"434ed950-40a4-4d81-84cf-7c86f1c102ed"},"_deposit":{"id":"210984","pid":{"type":"depid","value":"210984","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"最小数のエージェント群による動的グラフ探索","author_link":["535228","535226","535224","535229","535227","535225","535223","535230"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"最小数のエージェント群による動的グラフ探索"},{"subitem_title":"Exploration of dynamic graphs by the minimum number of agents","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2021-04-30","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"大阪大学大学院情報科学研究科"},{"subitem_text_value":"法政大学情報科学部"},{"subitem_text_value":"大阪大学大学院情報科学研究科"},{"subitem_text_value":"大阪大学大学院情報科学研究科"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Information Science and Technology Osaka University","subitem_text_language":"en"},{"subitem_text_value":" Faculty of Computer and Information Sciences\nHosei University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Science and Technology Osaka University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Science and Technology Osaka University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/210984/files/IPSJ-AL21183008.pdf","label":"IPSJ-AL21183008.pdf"},"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL21183008.pdf","filesize":[{"value":"960.2 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_login","version_id":"d542b706-c626-459a-ace9-9d0bea9a6468","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2021 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"飯塚, 俊介"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"首藤, 裕一"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"泉, 泰介"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"増澤, 利光"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Shunsuke, Iitsuka","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Yuichi, Sudo","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Taisuke, Izumi","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Toshimitsu, Masuzaawa","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"本稿では，利用可能な辺が時間とともに変動する動的グラフの探索問題において，グラフ全体が任意の時刻で連結であるという条件の下で，グラフ全体を探索するために必要なエージェント数について検討する．はじめに，同時に高々 ℓ 本の辺が消失する動的グラフに対し，探索に必要なエージェント数が少なくとも ℓ + 1 体であるような動的グラフが存在することを示す．次に，ℓ + 1 体のエージェントが存在するならば，任意の動的グラフを探索可能であることを，実際にアルゴリズムを提案することにより示す．最後に，提案アルゴリズムの探索時間は，動的グラフの頂点数を ????，辺数を ???? としたとき，???? ((8????????)ℓ+1) であることを示す．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"We consider the collaborative exploration of dynamic graphs by multiple agents, where dynamic graphs are defined as the ones whose edge set changes over (discrete) time, but the snapshot at each time is guaranteed to be connected. Our study focuses on the necessary and sufficient condition for the number of agents to attain the collaborative exploration in arbitrary dynamic graphs. First, we prove that in ℓ−bounded dynamic graphs, where at most ℓ edges can be disappeared at each time, ℓ + 1 agents are necessarily to explore all vertices. Then, we propose the algorithm which achieves the exploration using ℓ + 1 agents. The exploration time of the proposed algorithm is ???? ((8????????)ℓ+1), where ???? is the number of vertices, and ???? is the number of potential edges in dynamic graphs.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"6","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2021-04-30","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"8","bibliographicVolumeNumber":"2021-AL-183"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"updated":"2025-01-19T17:57:13.942904+00:00","created":"2025-01-19T01:12:10.913190+00:00","links":{}}