Efficient Enumeration Algorithm for Dominating Sets in Bounded Degenerate Graphs (Foundations and Applications of Algorithms and Computation)
-
- Kurita, Kazuhiro
- Graduate School of Information Science and Technology, Hokkaido University
-
- Wasa, Kunihiro
- National Institute of Informatics
-
- Arimura, Hiroki
- Graduate School of Information Science and Technology, Hokkaido University
-
- Uno, Takeaki
- National Institute of Informatics
Bibliographic Information
- Other Title
-
- Efficient Enumeration Algorithm for Dominating Sets in Bounded Degenerate Graphs
Search this article
Abstract
Dominating sets are fundamental graph structures. However, enumeration of dominating sets has not received much attention. This study aims to propose an efficient enumeration algorithms for bounded degenerate graphs. The algorithm enumerates all the dominating sets for k-degenerate graphs in O(k) time per solution using O(n+m) space. Since planar graphs have a constant degeneracy, this algorithm can enumerate all such sets for planar graphs in constant time per solution.
Journal
-
- RIMS Kokyuroku
-
RIMS Kokyuroku 2088 44-52, 2018-08
京都大学数理解析研究所
- Tweet
Details 詳細情報について
-
- CRID
- 1050566774764116864
-
- NII Article ID
- 120006861218
-
- NII Book ID
- AN00061013
-
- ISSN
- 18802818
-
- HANDLE
- 2433/251597
-
- NDL BIB ID
- 029523679
-
- Text Lang
- en
-
- Article Type
- departmental bulletin paper
-
- Data Source
-
- IRDB
- NDL
- CiNii Articles