Name
Abstract | ||
|---|---|---|
We show that all minimal dominating sets of a chordal bipartite graph can be generated in incremental polynomial, hence output polynomial, time. Enumeration of minimal dominating sets in graphs is equivalent to enumeration of minimal transversals in hypergraphs. Whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a well-studied and challenging question that has been open for several decades. With this result we contribute to the known cases having an affirmative reply to this important question. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.dam.2014.12.010 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Minimal dominating set,Enumeration,Output polynomial algorithm | Discrete mathematics,Dominating set,Combinatorics,Polynomial,Chordal graph,Chordal bipartite graph,Bipartite graph,Constraint graph,Hypergraph,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
199 | C | 0166-218X |
Citations | PageRank | References |
5 | 0.52 | 30 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petr A. Golovach | 1 | 766 | 83.25 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Mamadou Moustapha Kanté | 3 | 172 | 20.93 |
| Dieter Kratsch | 4 | 1957 | 146.89 |
| Yngve Villanger | 5 | 592 | 37.08 |