An improved algorithm for the nearly equitable edge-coloring problem
A nearly equitable edge-coloring of a multigraph is a coloring such that edges incident to each vertex are colored equitably in number. This problem was solved in O(kn(2)) time, where n and k are the numbers of the edges and the colors, respectively. The running time was improved to be O(n(2)/k + n\V\) later. We present a more efficient algorithm for this problem that runs in O(n(2)/k) time.
nearly equitable edge coloring euler circuit