An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem
Xuzhen Xie, Takao Ono, Shin-ichi Nakano, Tomio Hirata · Institutional Repositories DataBase (IRDB) · 2004
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.