An algorithm for finding a minimal edge coloring of a bipartite graph in time O(E log V) is presented. Polynomial time algorithms for this problem have previously been given by Gabow and Kariv the best time bounds being O(E log sq V) and O(V sq log V). The algorithm is based on using fast methods for finding maximal matchings in semiregular bipartite graphs; an algorithm for finding a maximal matching in a general bipartite graph was given by Hopcroft and Karp. Two algorithms for finding such a matching are given. Although the second one always has a faster running time, the first one is presented for the sake of clarity.
No takes yet. Share an insight, caveat, or question.
Cole et al. (1982) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: