{"created":"2023-05-15T12:00:49.194910+00:00","id":7780,"links":{},"metadata":{"_buckets":{"deposit":"db34b725-8439-44b0-90fa-1e8999e789a0"},"_deposit":{"created_by":3,"id":"7780","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"7780"},"status":"published"},"_oai":{"id":"oai:kyutech.repo.nii.ac.jp:00007780","sets":["8:24"]},"author_link":["34120","34121","6037","34123"],"control_number":"7780","item_1689815586683":{"attribute_name":"CRID","attribute_value_mlt":[{"subitem_relation_type":"isIdenticalTo","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://cir.nii.ac.jp/crid/1390001204381271552","subitem_relation_type_select":"URI"}}]},"item_21_alternative_title_18":{"attribute_name":"その他のタイトル","attribute_value_mlt":[{"subitem_alternative_title":"Complexity of the minimum single dominating cycle problem for graph classes","subitem_alternative_title_language":"en"}]},"item_21_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2018-03-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicPageEnd":"581","bibliographicPageStart":"574","bibliographicVolumeNumber":"E101.D","bibliographic_titles":[{"bibliographic_title":"IEICE Transactions on Information and Systems","bibliographic_titleLang":"en"}]}]},"item_21_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"In this paper, we study a variant of the Minimum Dominating Set problem. Given an unweighted undirected graph G=(V,E) of n=|V| vertices, the goal of the Minimum Single Dominating Cycle problem (MinSDC) is to find a single shortest cycle which dominates all vertices, i.e., a cycle C such that for the set V(C) of vertices in C and the set N(V(C)) of neighbor vertices of C, V(G)=V(C)∪N(V(C)) and |V(C)| is minimum over all dominating cycles in G [6], [17], [24]. In this paper we consider the (in)approximability of MinSDC if input graphs are restricted to some special classes of graphs. We first show that MinSDC is still NP-hard to approximate even when restricted to planar, bipartite, chordal, or r-regular (r≥3). Then, we show the (lnn+1)-approximability and the (1-ε)lnn-inapproximability of MinSDC on split graphs under P≠NP. Furthermore, we explicitly design a linear-time algorithm to solve MinSDC for graphs with bounded treewidth and estimate the hidden constant factor of its running time-bound.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_21_link_62":{"attribute_name":"研究者情報","attribute_value_mlt":[{"subitem_link_url":"https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html"}]},"item_21_publisher_7":{"attribute_name":"出版社","attribute_value_mlt":[{"subitem_publisher":"電子情報通信学会","subitem_publisher_language":"ja"}]},"item_21_relation_12":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isIdenticalTo","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1587/transinf.2017FCP0007","subitem_relation_type_select":"DOI"}}]},"item_21_rights_13":{"attribute_name":"著作権関連情報","attribute_value_mlt":[{"subitem_rights":"Copyright (c) 2018 The Institute of Electronics, Information and Communication Engineers"}]},"item_21_select_59":{"attribute_name":"査読の有無","attribute_value_mlt":[{"subitem_select_item":"yes"}]},"item_21_source_id_10":{"attribute_name":"NCID","attribute_value_mlt":[{"subitem_source_identifier":"AA10826272","subitem_source_identifier_type":"NCID"}]},"item_21_source_id_8":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1745-1361","subitem_source_identifier_type":"EISSN"},{"subitem_source_identifier":"0916-8532","subitem_source_identifier_type":"PISSN"}]},"item_21_text_28":{"attribute_name":"論文ID（連携）","attribute_value_mlt":[{"subitem_text_value":"10315885"}]},"item_21_text_63":{"attribute_name":"連携ID","attribute_value_mlt":[{"subitem_text_value":"10662"}]},"item_21_version_type_58":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorAlternatives":[{"creatorAlternative":"Eto, H.","creatorAlternativeLang":"en"}],"creatorNames":[{"creatorName":"Eto, Hiroshi","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorAlternatives":[{"creatorAlternative":"Kawahara, H.","creatorAlternativeLang":"en"}],"creatorNames":[{"creatorName":"Kawahara, Hiroyuki","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorAffiliations":[{"affiliationNames":[{}]}],"creatorNames":[{"creatorName":"Miyano, Eiji","creatorNameLang":"en"},{"creatorName":"宮野, 英次","creatorNameLang":"ja"},{"creatorName":"ミヤノ, エイジ","creatorNameLang":"ja-Kana"}],"familyNames":[{},{},{}],"givenNames":[{},{},{}],"nameIdentifiers":[{},{},{},{},{}]},{"creatorAlternatives":[{"creatorAlternative":"Nonoue, N.","creatorAlternativeLang":"en"}],"creatorNames":[{"creatorName":"Nonoue, Natsuki","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2022-10-03"}],"displaytype":"detail","filename":"E101.D_2017FCP0007.pdf","filesize":[{"value":"467.6 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"E101.D_2017FCP0007.pdf","url":"https://kyutech.repo.nii.ac.jp/record/7780/files/E101.D_2017FCP0007.pdf"},"version_id":"7c35588c-d212-4e11-9433-652f779468ca"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"minimum single dominating problem","subitem_subject_scheme":"Other"},{"subitem_subject":"graph classes","subitem_subject_scheme":"Other"},{"subitem_subject":"(in)tractability","subitem_subject_scheme":"Other"},{"subitem_subject":"(in)approximability","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Complexity of the Minimum Single Dominating Cycle Problem for Graph Classes","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Complexity of the Minimum Single Dominating Cycle Problem for Graph Classes","subitem_title_language":"en"}]},"item_type_id":"21","owner":"3","path":["24"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2022-10-03"},"publish_date":"2022-10-03","publish_status":"0","recid":"7780","relation_version_is_last":true,"title":["Complexity of the Minimum Single Dominating Cycle Problem for Graph Classes"],"weko_creator_id":"3","weko_shared_id":-1},"updated":"2024-01-26T06:52:25.645072+00:00"}