Kurita, Kazuhiro ;
Wasa, Kunihiro ;
Arimura, Hiroki ;
Uno, Takeaki
Efficient Enumeration of Dominating Sets for Sparse Graphs
Abstract
A dominating set D of a graph G is a set of vertices such that any vertex in G is in D or its neighbor is in D. Enumeration of minimal dominating sets in a graph is one of central problems in enumeration study since enumeration of minimal dominating sets corresponds to enumeration of minimal hypergraph transversal. However, enumeration of dominating sets including nonminimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a kdegenerate graph in O(k) time per solution using O(n + m) space, where n and m are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, Hminor free graphs with some fixed H. The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine.
BibTeX  Entry
@InProceedings{kurita_et_al:LIPIcs:2018:9956,
author = {Kazuhiro Kurita and Kunihiro Wasa and Hiroki Arimura and Takeaki Uno},
title = {{Efficient Enumeration of Dominating Sets for Sparse Graphs}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {8:18:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9956},
URN = {urn:nbn:de:0030drops99560},
doi = {10.4230/LIPIcs.ISAAC.2018.8},
annote = {Keywords: Enumeration algorithm, polynomial amortized time, dominating set, girth, degeneracy}
}
06.12.2018
Keywords: 

Enumeration algorithm, polynomial amortized time, dominating set, girth, degeneracy 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

06.12.2018 