Article ID: | iaor201526361 |
Volume: | 72 |
Issue: | 3 |
Start Page Number: | 836 |
End Page Number: | 859 |
Publication Date: | Jul 2015 |
Journal: | Algorithmica |
Authors: | Kratsch Dieter, Heggernes Pinar, Villanger Yngve, Golovach Petr |
Keywords: | graphs, sets |
We show that all minimal edge dominating sets of a graph can be generated in incremental polynomial time. We present an algorithm that solves the equivalent problem of enumerating minimal (vertex) dominating sets of line graphs in incremental polynomial, and consequently output polynomial, time. Enumeration of minimal dominating sets in graphs has recently been shown to be equivalent to enumeration of minimal transversals in hypergraphs. The question whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a fundamental and challenging question; it has been open for several decades and has triggered extensive research. To obtain our result, we present a flipping method to generate all minimal dominating sets of a graph. Its basic idea is to apply a flipping operation to a minimal dominating set