Another simple algorithm for edge-coloring bipartite graphs
A new edge-coloring algorithm for bipartite graphs is presented. This algorithm, based on the framework of the O(m log d + (m/d) log(m/d) log d) algorithm by Makino-Takabatake-Fujishige and the O(m log m) one by Alon, finds an optimal edge-coloring of a bipartite graph with m edges and maximum degree d in O(m log d + (m/d) log(m/d)) time. This algorithm does not require elaborate data structures, which the best known O(m log d) algorithm due to Cole-Ost-Schirra depends on.
edge-coloring bipartite matching graph algorithms combinatorial optimization