P204: Enumeration of all minimal edge-dominating sets in a graph

P204: Enumeration of all minimal edge-dominating sets in a graph

Input:

A graph $G$.

Output:

All minimal edge-dominating sets in $G$.

Complexity:

$O(||L(G)||^5N^6)$ total time.

Comment:

$L(G)$ is the line graph of $G$, $||L(G)||$ is the size of $L(G)$, and $N$ is the number of minimal edge-dominating sets in $G$.

Reference:

[Kante2012] (Bibtex)