On the Enumeration of Minimal Dominating Sets and Related Notions. Kanté, Moustapha, M., Limouzy, V., Mary, A., & Nourine, L. SIAM Journal on Discrete Mathematics, 28(4):1916--1929, Society for Industrial and Applied Mathematics, November, 2014.
On the Enumeration of Minimal Dominating Sets and Related Notions [link]Paper  doi  abstract   bibtex   
A dominating set \$D\$ in a graph is a subset of its vertex set such that each vertex is either in \$D\$ or has a neighbor in \$D\$. In this paper, we are interested in the enumeration of (inclusionwise) minimal dominating sets in graphs, called the Dom-Enum problem. It is well known that this problem can be polynomially reduced to the Trans-Enum problem in hypergraphs, i.e., the problem of enumerating all minimal transversals in a hypergraph. First, we show that the Trans-Enum problem can be polynomially reduced to the Dom-Enum problem. As a consequence there exists an output-polynomial time algorithm for the Trans-Enum problem if and only if there exists one for the Dom-Enum problem. Second, we study the Dom-Enum problem in some graph classes. We give an output-polynomial time algorithm for the Dom-Enum problem in split graphs and introduce the completion of a graph to obtain an output-polynomial time algorithm for the Dom-Enum problem in \$P_6\$-free chordal graphs, a proper superclass of split graphs. Finally‥.
@article{ Kante2014,
  abstract = {A dominating set \$D\$ in a graph is a subset of its vertex set such that each vertex is either in \$D\$ or has a neighbor in \$D\$. In this paper, we are interested in the enumeration of (inclusionwise) minimal dominating sets in graphs, called the Dom-Enum problem. It is well known that this problem can be polynomially reduced to the Trans-Enum problem in hypergraphs, i.e., the problem of enumerating all minimal transversals in a hypergraph. First, we show that the Trans-Enum problem can be polynomially reduced to the Dom-Enum problem. As a consequence there exists an output-polynomial time algorithm for the Trans-Enum problem if and only if there exists one for the Dom-Enum problem. Second, we study the Dom-Enum problem in some graph classes. We give an output-polynomial time algorithm for the Dom-Enum problem in split graphs and introduce the completion of a graph to obtain an output-polynomial time algorithm for the Dom-Enum problem in \$P_6\$-free chordal graphs, a proper superclass of split graphs. Finally‥.},
  author = {Kanté, Mamadou Moustapha and Limouzy, Vincent and Mary, Arnaud and Nourine, Lhouari},
  doi = {10.1137/120862612},
  file = {:Users/KunihiroWASA/Dropbox/paper/2014/Kanté et al., On the Enumeration of Minimal Dominating Sets and Related Notions, 2014.pdf:pdf},
  issn = {0895-4801},
  journal = {SIAM Journal on Discrete Mathematics},
  keywords = {05C30,05C65,05C69,05C85,68R05,68R10,hypergraph dualization,minimal (connected,output polynomial time algorithm,total) dominating set enumeration,transversal problem},
  language = {en},
  month = {November},
  number = {4},
  pages = {1916--1929},
  publisher = {Society for Industrial and Applied Mathematics},
  title = {{On the Enumeration of Minimal Dominating Sets and Related Notions}},
  url = {http://epubs.siam.org/doi/abs/10.1137/120862612},
  volume = {28},
  year = {2014}
}

Downloads: 0