  For an arbitrary undirected simple graph G with m edges, we give an algorithm
with running time O(m^4 |L|^2) to generate the set L of all minimal edge
dominating sets of G. For bipartite graphs we obtain a better result; we show
that their minimal edge dominating sets can be enumerated in time O(m^4 |L|).
In fact our results are stronger; both algorithms generate the next minimal
edge dominating set with incremental-polynomial delay O(m^5 |L|) and O(m^4 |L|)
respectively, when L is the set of already generated minimal edge dominating
sets. Our algorithms are tailored for and solve the equivalent problems of
enumerating minimal (vertex) dominating sets of line graphs and line graphs of
bipartite graphs, with incremental-polynomial delay, and consequently in
output-polynomial time. Enumeration of minimal dominating sets in graphs has
very 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 in Output-Sensitive Enumeration; it has been open for
several decades and has triggered extensive research in the field.

Data Structures and Algorithms;Discrete Mathematics;Combinatorics