{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00218742","sets":["1164:5305:10889:10954"]},"path":["10954"],"owner":"44499","recid":"218742","title":["Winner Determination Algorithms for Colored Arc Kayles"],"pubdate":{"attribute_name":"公開日","attribute_value":"2022-06-25"},"_buckets":{"deposit":"f3f7d321-10fd-480d-87f8-8744f4223746"},"_deposit":{"id":"218742","pid":{"type":"depid","value":"218742","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Winner Determination Algorithms for Colored Arc Kayles","author_link":["569535","569539","569537","569533","569538","569534","569540","569536"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Winner Determination Algorithms for Colored Arc Kayles"},{"subitem_title":"Winner Determination Algorithms for Colored Arc Kayles","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"その他のゲーム","subitem_subject_scheme":"Other"}]},"item_type_id":"4","publish_date":"2022-06-25","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Nagoya University"},{"subitem_text_value":"Kyushu University"},{"subitem_text_value":"Kyushu University"},{"subitem_text_value":"Nagoya University"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Nagoya University","subitem_text_language":"en"},{"subitem_text_value":"Kyushu University","subitem_text_language":"en"},{"subitem_text_value":"Kyushu University","subitem_text_language":"en"},{"subitem_text_value":"Nagoya University","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/218742/files/IPSJ-GI22048012.pdf","label":"IPSJ-GI22048012.pdf"},"date":[{"dateType":"Available","dateValue":"2024-06-25"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-GI22048012.pdf","filesize":[{"value":"693.5 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":"18"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"d6af61f7-162a-44a2-ad2f-be2e401a2381","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2022 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kanae, Yoshiwatari"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hironori, Kiya"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Tesshu, Hanaka"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hirotaka, Ono"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kanae, Yoshiwatari","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hironori, Kiya","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Tesshu, Hanaka","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hirotaka, Ono","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11362144","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-8736","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a matching. In this paper, we define a generalized game called Colored Arc Kayles, which includes these games. Colored Arc Kayles is played on a graph whose edges are colored in black, white, or gray, and black (resp., white) edges can be selected only by the black (resp., white) player, although gray edges can be selected by both black and white players. BW-Arc Kayles and Arc Kayles are restrictions of Colored Arc Kayles, where We first observe that the winner determination for Colored Arc Kayles can be done in O*(2n) time by a simple algorithm, where n is the order of a graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are solved in time O*(1.4143τ2+3.17τ), O*(1.3161τ2+4τ), and O*(1.1893τ2+6.34τ), respectively, where τ is the vertex cover number. Furthermore, we present an O*((n/ν + 1)ν)-time algorithm for Arc Kayles, where ν is neighborhood diversity. We finally show that Arc Kayles on trees can be solved in O*(2n/2)(= O(1.4143n)) time, which improves O*(3n/3)(= O(1.4423n)) by a direct adjustment of the analysis of Bodlaender et al.'s O*(3n/3)-time algorithm for Node Kayles.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a matching. In this paper, we define a generalized game called Colored Arc Kayles, which includes these games. Colored Arc Kayles is played on a graph whose edges are colored in black, white, or gray, and black (resp., white) edges can be selected only by the black (resp., white) player, although gray edges can be selected by both black and white players. BW-Arc Kayles and Arc Kayles are restrictions of Colored Arc Kayles, where We first observe that the winner determination for Colored Arc Kayles can be done in O*(2n) time by a simple algorithm, where n is the order of a graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are solved in time O*(1.4143τ2+3.17τ), O*(1.3161τ2+4τ), and O*(1.1893τ2+6.34τ), respectively, where τ is the vertex cover number. Furthermore, we present an O*((n/ν + 1)ν)-time algorithm for Arc Kayles, where ν is neighborhood diversity. We finally show that Arc Kayles on trees can be solved in O*(2n/2)(= O(1.4143n)) time, which improves O*(3n/3)(= O(1.4423n)) by a direct adjustment of the analysis of Bodlaender et al.'s O*(3n/3)-time algorithm for Node Kayles.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"5","bibliographic_titles":[{"bibliographic_title":"研究報告ゲーム情報学（GI）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2022-06-25","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"12","bibliographicVolumeNumber":"2022-GI-48"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":218742,"updated":"2025-01-19T15:03:07.130635+00:00","links":{},"created":"2025-01-19T01:19:05.423120+00:00"}