Edge-Coloring Bipartite Multigraphs in 0(E log D) Time

Richard Cole, Kirstin Ost

Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G.  We show that a minimal edge-coloring of G can be computed in O(E log D) time.  This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time.