{"created":"2025-01-19T01:28:04.503741+00:00","updated":"2025-01-19T11:39:48.984212+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00228944","sets":["1164:2592:11085:11360"]},"path":["11360"],"owner":"44499","recid":"228944","title":["On the Problems of Finding Paths to Avoid Ordered Forbidden Transitions Based on Graph Structure"],"pubdate":{"attribute_name":"公開日","attribute_value":"2023-11-09"},"_buckets":{"deposit":"095e13a2-62f5-4c64-9784-e08b840ccd1d"},"_deposit":{"id":"228944","pid":{"type":"depid","value":"228944","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"On the Problems of Finding Paths to Avoid Ordered Forbidden Transitions Based on Graph Structure","author_link":["614871","614870","614866","614872","614867","614873","614868","614869"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"On the Problems of Finding Paths to Avoid Ordered Forbidden Transitions Based on Graph Structure"},{"subitem_title":"On the Problems of Finding Paths to Avoid Ordered Forbidden Transitions Based on Graph Structure","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2023-11-09","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University"},{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University"},{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University"},{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Sciences, Tohoku University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Sciences, Tohoku 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/228944/files/IPSJ-AL23195024.pdf","label":"IPSJ-AL23195024.pdf"},"date":[{"dateType":"Available","dateValue":"2025-11-09"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL23195024.pdf","filesize":[{"value":"1.1 MB"}],"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":"f65fbd80-f9a8-4fb1-a408-32f3c096feec","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2023 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kota, Kumakura"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Akira, Suzuki"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Yuma, Tamura"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Xiao, Zhou"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kota, Kumakura","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Akira, Suzuki","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Yuma, Tamura","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Xiao, Zhou","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":"Finding a path between two vertices of a given graph is one of the most classic problems in graph theory. Recently, problems of finding a route avoiding forbidden transitions, that is, two edges that cannot be passed through consecutively, have been studied. In this paper, we introduce the ordered variants of these problems, namely the Path Avoiding Ordered Forbidden Transitions problem (PAOFT for short) and the Trail Avoiding Ordered Forbidden Transitions problem (TAOFT for short). We show that both the problems are NP-complete even for bipartite planar graphs with maximum degree three. Furthermore, we show that TAOFT remains NP-complete for cactus graphs. As positive results of PAOFT, we give a polynomial-time algorithm for bounded treewidth graphs and a linear-time algorithm for cactus graphs.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Finding a path between two vertices of a given graph is one of the most classic problems in graph theory. Recently, problems of finding a route avoiding forbidden transitions, that is, two edges that cannot be passed through consecutively, have been studied. In this paper, we introduce the ordered variants of these problems, namely the Path Avoiding Ordered Forbidden Transitions problem (PAOFT for short) and the Trail Avoiding Ordered Forbidden Transitions problem (TAOFT for short). We show that both the problems are NP-complete even for bipartite planar graphs with maximum degree three. Furthermore, we show that TAOFT remains NP-complete for cactus graphs. As positive results of PAOFT, we give a polynomial-time algorithm for bounded treewidth graphs and a linear-time algorithm for cactus graphs.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"5","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2023-11-09","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"24","bibliographicVolumeNumber":"2023-AL-195"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":228944,"links":{}}