WEKO3
アイテム
{"_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": ["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_text": "https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html", "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": [{"nameIdentifier": "34120", "nameIdentifierScheme": "WEKO"}]}, {"creatorAlternatives": [{"creatorAlternative": "Kawahara, H.", "creatorAlternativeLang": "en"}], "creatorNames": [{"creatorName": "Kawahara, Hiroyuki", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "34121", "nameIdentifierScheme": "WEKO"}]}, {"creatorAffiliations": [{"affiliationNames": [{"affiliationNameLang": "ja"}]}], "creatorNames": [{"creatorName": "Miyano, Eiji", "creatorNameLang": "en"}, {"creatorName": "宮野, 英次", "creatorNameLang": "ja"}, {"creatorName": "ミヤノ, エイジ", "creatorNameLang": "ja-Kana"}], "familyNames": [{"familyName": "Miyano", "familyNameLang": "en"}, {"familyName": "宮野", "familyNameLang": "ja"}, {"familyName": "ミヤノ", "familyNameLang": "ja-Kana"}], "givenNames": [{"givenName": "Eiji", "givenNameLang": "en"}, {"givenName": "英次", "givenNameLang": "ja"}, {"givenName": "エイジ", "givenNameLang": "ja-Kana"}], "nameIdentifiers": [{"nameIdentifier": "6037", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "10284548", "nameIdentifierScheme": "e-Rad", "nameIdentifierURI": "https://nrid.nii.ac.jp/ja/nrid/1000010284548"}, {"nameIdentifier": "6603649200", "nameIdentifierScheme": "Scopus著者ID", "nameIdentifierURI": "https://www.scopus.com/authid/detail.uri?authorId=6603649200"}, {"nameIdentifier": "0000-0002-4260-7818", "nameIdentifierScheme": "ORCiD", "nameIdentifierURI": "https://orcid.org/0000-0002-4260-7818"}, {"nameIdentifier": "233", "nameIdentifierScheme": "九工大研究者情報", "nameIdentifierURI": "https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html"}]}, {"creatorAlternatives": [{"creatorAlternative": "Nonoue, N.", "creatorAlternativeLang": "en"}], "creatorNames": [{"creatorName": "Nonoue, Natsuki", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "34123", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2022-10-03"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "E101.D_2017FCP0007.pdf", "filesize": [{"value": "467.6 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 467600.0, "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"], "permalink_uri": "http://hdl.handle.net/10228/00008983", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2022-10-03"}, "publish_date": "2022-10-03", "publish_status": "0", "recid": "7780", "relation": {}, "relation_version_is_last": true, "title": ["Complexity of the Minimum Single Dominating Cycle Problem for Graph Classes"], "weko_shared_id": -1}
Complexity of the Minimum Single Dominating Cycle Problem for Graph Classes
http://hdl.handle.net/10228/00008983
http://hdl.handle.net/10228/000089832b2a5c3c-0895-46f0-8fc5-65a818c18bb9
名前 / ファイル | ライセンス | アクション |
---|---|---|
E101.D_2017FCP0007.pdf (467.6 kB)
|
|
Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2022-10-03 | |||||||||||
資源タイプ | ||||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
資源タイプ | journal article | |||||||||||
タイトル | ||||||||||||
言語 | en | |||||||||||
タイトル | Complexity of the Minimum Single Dominating Cycle Problem for Graph Classes | |||||||||||
その他のタイトル | ||||||||||||
その他のタイトル | Complexity of the minimum single dominating cycle problem for graph classes | |||||||||||
言語 | en | |||||||||||
言語 | ||||||||||||
言語 | eng | |||||||||||
著者 |
Eto, Hiroshi
× Eto, Hiroshi× Kawahara, Hiroyuki× 宮野, 英次
WEKO
6037
× Nonoue, Natsuki |
|||||||||||
抄録 | ||||||||||||
内容記述タイプ | Abstract | |||||||||||
内容記述 | 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. | |||||||||||
言語 | en | |||||||||||
書誌情報 |
en : IEICE Transactions on Information and Systems 巻 E101.D, 号 3, p. 574-581, 発行日 2018-03-01 |
|||||||||||
出版社 | ||||||||||||
言語 | ja | |||||||||||
出版者 | 電子情報通信学会 | |||||||||||
DOI | ||||||||||||
関連タイプ | isIdenticalTo | |||||||||||
識別子タイプ | DOI | |||||||||||
関連識別子 | https://doi.org/10.1587/transinf.2017FCP0007 | |||||||||||
CRID | ||||||||||||
関連タイプ | isIdenticalTo | |||||||||||
識別子タイプ | URI | |||||||||||
関連識別子 | https://cir.nii.ac.jp/crid/1390001204381271552 | |||||||||||
NCID | ||||||||||||
収録物識別子タイプ | NCID | |||||||||||
収録物識別子 | AA10826272 | |||||||||||
ISSN | ||||||||||||
収録物識別子タイプ | EISSN | |||||||||||
収録物識別子 | 1745-1361 | |||||||||||
ISSN | ||||||||||||
収録物識別子タイプ | PISSN | |||||||||||
収録物識別子 | 0916-8532 | |||||||||||
著作権関連情報 | ||||||||||||
権利情報 | Copyright (c) 2018 The Institute of Electronics, Information and Communication Engineers | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | minimum single dominating problem | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | graph classes | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | (in)tractability | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | (in)approximability | |||||||||||
出版タイプ | ||||||||||||
出版タイプ | VoR | |||||||||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||
査読の有無 | ||||||||||||
値 | yes | |||||||||||
研究者情報 | ||||||||||||
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | ||||||||||||
論文ID(連携) | ||||||||||||
10315885 | ||||||||||||
連携ID | ||||||||||||
10662 |