@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}
}

{"_id":"ikrNr6QryWxZ3mQPX","authorIDs":[],"author_short":["Kanté","Moustapha, M.","Limouzy, V.","Mary, A.","Nourine, L."],"bibbaseid":"kant-moustapha-limouzy-mary-nourine-ontheenumerationofminimaldominatingsetsandrelatednotions-2014","bibdata":{"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é","Moustapha, Mamadou","Limouzy, Vincent","Mary, Arnaud","Nourine, Lhouari"],"author_short":["Kanté","Moustapha, M.","Limouzy, V.","Mary, A.","Nourine, L."],"bibtex":"@article{ Kante2014,\n 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‥.},\n author = {Kanté, Mamadou Moustapha and Limouzy, Vincent and Mary, Arnaud and Nourine, Lhouari},\n doi = {10.1137/120862612},\n file = {:Users/KunihiroWASA/Dropbox/paper/2014/Kanté et al., On the Enumeration of Minimal Dominating Sets and Related Notions, 2014.pdf:pdf},\n issn = {0895-4801},\n journal = {SIAM Journal on Discrete Mathematics},\n keywords = {05C30,05C65,05C69,05C85,68R05,68R10,hypergraph dualization,minimal (connected,output polynomial time algorithm,total) dominating set enumeration,transversal problem},\n language = {en},\n month = {November},\n number = {4},\n pages = {1916--1929},\n publisher = {Society for Industrial and Applied Mathematics},\n title = {{On the Enumeration of Minimal Dominating Sets and Related Notions}},\n url = {http://epubs.siam.org/doi/abs/10.1137/120862612},\n volume = {28},\n year = {2014}\n}","bibtype":"article","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","id":"Kante2014","issn":"0895-4801","journal":"SIAM Journal on Discrete Mathematics","key":"Kante2014","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","type":"article","url":"http://epubs.siam.org/doi/abs/10.1137/120862612","volume":"28","year":"2014","bibbaseid":"kant-moustapha-limouzy-mary-nourine-ontheenumerationofminimaldominatingsetsandrelatednotions-2014","role":"author","urls":{"Paper":"http://epubs.siam.org/doi/abs/10.1137/120862612"},"keyword":["05C30","05C65","05C69","05C85","68R05","68R10","hypergraph dualization","minimal (connected","output polynomial time algorithm","total) dominating set enumeration","transversal problem"],"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:44.536Z","downloads":0,"keywords":["05c30","05c65","05c69","05c85","68r05","68r10","hypergraph dualization","minimal (connected","output polynomial time algorithm","total) dominating set enumeration","transversal problem"],"search_terms":["enumeration","minimal","dominating","sets","related","notions","kanté","moustapha","limouzy","mary","nourine"],"title":"On the Enumeration of Minimal Dominating Sets and Related Notions","year":2014,"dataSources":["YRMeqhMHoNu9HzJoC"]}