Another Simple Algorithm for Edge-Coloring Bipartite Graphs
Toshinori Takabatake · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2005
A new edge-coloring algorithm for bipartite graphs is presented. This algorithm, based on the framework of the O(mlogd + (m/d)log(m/d)log d) algorithm by Makino--Takabatake--Fujishige and the O(mlogm) one by Alon, finds an optimal edge-coloring of a bipartite graph with m edges and maximum degree d in O(mlogd + (m/d)log(m/d)) time. This algorithm does not require elaborate data structures, which the best known O(mlogd) algorithm due to Cole--Ost--Schirra depends on.