Efficient Enumeration Algorithm for Dominating Sets in Bounded Degenerate Graphs
書誌事項
- タイトル別名
-
- Efficient Enumeration Algorithm for Dominating Sets in Bounded Degenerate Graphs (Foundations and Applications of Algorithms and Computation)
この論文をさがす
抄録
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.
収録刊行物
-
- 数理解析研究所講究録
-
数理解析研究所講究録 2088 44-52, 2018-08
京都大学数理解析研究所
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1050566774764116864
-
- NII論文ID
- 120006861218
-
- NII書誌ID
- AN00061013
-
- ISSN
- 18802818
-
- HANDLE
- 2433/251597
-
- NDL書誌ID
- 029523679
-
- 本文言語コード
- en
-
- 資料種別
- departmental bulletin paper
-
- データソース種別
-
- IRDB
- NDL
- CiNii Articles