Complexity of the Minimum Single Dominating Cycle Problem for Graph Classes
-
- ETO Hiroshi
- Kyushu University
-
- KAWAHARA Hiroyuki
- Kyushu Insitute of Technology
-
- MIYANO Eiji
- Kyushu Insitute of Technology
-
- NONOUE Natsuki
- Kyushu Insitute of Technology
この論文をさがす
抄録
<p>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.</p>
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E101.D (3), 574-581, 2018
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390001204381271552
-
- NII論文ID
- 130006414058
-
- NII書誌ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- HANDLE
- 10228/00008983
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可