WEKO3
アイテム
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)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-10-03 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Complexity of the Minimum Single Dominating Cycle Problem for Graph Classes | |||||||||||||
| 言語 | en | |||||||||||||
| その他のタイトル | ||||||||||||||
| その他のタイトル | 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 | |||||||||||||
| 研究者情報 | ||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||
| 論文ID（連携） | ||||||||||||||
| 値 | 10315885 | |||||||||||||
| 連携ID | ||||||||||||||
| 値 | 10662 | |||||||||||||
