P86: Enumeration of all the edge colorings of a bipartite graph

P86: Enumeration of all the edge colorings of a bipartite graph

Input:

A bipartite graph $B = (V, E)$.

Output:

All the edge colorings pf $B$.

Complexity:

$O(T(|V|+|E|+\Delta) + K \min \{|V|^2 + |E|, T(|V|, |E|, \Delta)\})$ total time and $O(|E|\Delta)$ space.

Comment:

$\Delta$ is the number of maximum degree and $T(|V|, |E|, \Delta)$ is the time complexity of an edge coloring algorithm.

Reference:

[Matsui1996b] (Bibtex)