{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00072907","sets":["1164:2592:6240:6332"]},"path":["6332"],"owner":"10","recid":"72907","title":["Hardness and FPT Algorithm for the Rainbow Connectivity of Graphs"],"pubdate":{"attribute_name":"公開日","attribute_value":"2011-02-28"},"_buckets":{"deposit":"014b155a-5bd1-4a59-ae35-308cee4624ca"},"_deposit":{"id":"72907","pid":{"type":"depid","value":"72907","revision_id":0},"owners":[10],"status":"published","created_by":10},"item_title":"Hardness and FPT Algorithm for the Rainbow Connectivity of Graphs","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Hardness and FPT Algorithm for the Rainbow Connectivity of Graphs"},{"subitem_title":"Hardness and FPT Algorithm for the Rainbow Connectivity of Graphs","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2011-02-28","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."},{"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"},{"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/72907/files/IPSJ-AL11134004.pdf"},"date":[{"dateType":"Available","dateValue":"2013-02-28"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL11134004.pdf","filesize":[{"value":"297.6 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":"4480a345-4f07-49ce-b74f-a292b9defb88","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2011 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Takanori, Aoki"},{"creatorName":"Takehiro, Ito"},{"creatorName":"Akira, Suzuki"},{"creatorName":"Kei, Uchizawa"},{"creatorName":"Xiao, Zhou"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Takanori, Aoki","creatorNameLang":"en"},{"creatorName":"Takehiro, Ito","creatorNameLang":"en"},{"creatorName":"Akira, Suzuki","creatorNameLang":"en"},{"creatorName":"Kei, Uchizawa","creatorNameLang":"en"},{"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_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"For a graph G = (V,E) and a color set C, let f : E → C be an edge-coloring of G which is not necessarily proper. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G has a path in which all edges are assigned distinct colors by f. In this paper, we give three results for the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. The first is to show that the problem is strongly NP-complete even for outerplanar graphs. We also show that the problem is strongly NP-complete for graphs of diameter 2. In contrast, as the second result, we show that the problem can be solved in polynomial time for cacti. Notice that both outerplanar graphs and cacti are of treewidth 2, and hence our complexity analysis is precise in some sense. The third is to give an FPT algorithm for general graphs when parameterized by the number of colors in C; this result implies that the problem can be solved in polynomial time for general graphs with n vertices if |C| = O(log n).","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"For a graph G = (V,E) and a color set C, let f : E → C be an edge-coloring of G which is not necessarily proper. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G has a path in which all edges are assigned distinct colors by f. In this paper, we give three results for the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. The first is to show that the problem is strongly NP-complete even for outerplanar graphs. We also show that the problem is strongly NP-complete for graphs of diameter 2. In contrast, as the second result, we show that the problem can be solved in polynomial time for cacti. Notice that both outerplanar graphs and cacti are of treewidth 2, and hence our complexity analysis is precise in some sense. The third is to give an FPT algorithm for general graphs when parameterized by the number of colors in C; this result implies that the problem can be solved in polynomial time for general graphs with n vertices if |C| = O(log n).","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2011-02-28","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"4","bibliographicVolumeNumber":"2011-AL-134"}]},"relation_version_is_last":true,"weko_creator_id":"10"},"id":72907,"updated":"2025-01-21T22:08:53.093161+00:00","links":{},"created":"2025-01-18T23:31:04.968378+00:00"}