- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- 【Updated on June 30, 2025】Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
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
Search this article
Description
<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>
Journal
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E101.D (3), 574-581, 2018
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1390001204381271552
-
- NII Article ID
- 130006414058
-
- NII Book ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- HANDLE
- 10228/00008983
-
- Text Lang
- en
-
- Article Type
- journal article
-
- Data Source
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
- KAKEN
- OpenAIRE
-
- Abstract License Flag
- Disallowed