{"updated":"2025-01-20T13:11:40.779457+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00157890","sets":["1164:2592:8452:8603"]},"path":["8603"],"owner":"11","recid":"157890","title":["Sliding tokens on unicyclic graphs"],"pubdate":{"attribute_name":"公開日","attribute_value":"2016-02-28"},"_buckets":{"deposit":"478f5081-9ab2-44d7-81f1-aca514068783"},"_deposit":{"id":"157890","pid":{"type":"depid","value":"157890","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"Sliding tokens on unicyclic graphs","author_link":["300003","300002","300001","300004"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Sliding tokens on unicyclic graphs"},{"subitem_title":"Sliding tokens on unicyclic graphs","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2016-02-28","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Japan Advanced Institute of Science and Technology"},{"subitem_text_value":"Japan Advanced Institute of Science and Technology"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Japan Advanced Institute of Science and Technology","subitem_text_language":"en"},{"subitem_text_value":"Japan Advanced Institute of Science and Technology","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"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/157890/files/IPSJ-AL16157005.pdf","label":"IPSJ-AL16157005.pdf"},"date":[{"dateType":"Available","dateValue":"2018-02-28"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL16157005.pdf","filesize":[{"value":"660.0 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"a3220289-73c0-4f1d-9b6d-a1675878f93a","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2016 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Duc, A. Hoang"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Ryuhei, Uehara"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Duc, A. Hoang","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Ryuhei, Uehara","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":"Given two independent sets I and J (having the same cardinality) of a graph G, and imagine that a token (coin) is placed on each vertex in I. Then, the sliding token problem asks if one could transforms I to J using a sequence of elementary steps, where each step requires sliding a token from one vertex to one of its neighbors such that the resulting set of vertices where tokens are placed still remains independent. Interestingly, on some graph classes such as trees, bipartite graphs, unicyclic graphs, etc., sometimes the tokens are required to make “detours” in order not to violate the independence property. This makes the sliding token problem more complicated and challenged. In this paper, based on the idea of Demaine et al. [4], we present a polynomial-time algorithm for SOLVING SLIDING TOKEN on unicyclic graphs.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Given two independent sets I and J (having the same cardinality) of a graph G, and imagine that a token (coin) is placed on each vertex in I. Then, the sliding token problem asks if one could transforms I to J using a sequence of elementary steps, where each step requires sliding a token from one vertex to one of its neighbors such that the resulting set of vertices where tokens are placed still remains independent. Interestingly, on some graph classes such as trees, bipartite graphs, unicyclic graphs, etc., sometimes the tokens are required to make “detours” in order not to violate the independence property. This makes the sliding token problem more complicated and challenged. In this paper, based on the idea of Demaine et al. [4], we present a polynomial-time algorithm for SOLVING SLIDING TOKEN on unicyclic graphs.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"7","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2016-02-28","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicVolumeNumber":"2016-AL-157"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"created":"2025-01-19T00:31:42.186595+00:00","id":157890,"links":{}}