Geodesic
A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions
Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 391-407.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We discuss the nearly equitable edge coloring problem on a multigraph and propose an efficient algorithm for solving the problem, which has a better time complexity than the previous algorithms. The coloring computed by our algorithm satisfies additional balanced conditions on the number of edges used in each color class, where conditions are imposed on the balance among all edges in the multigraph as well as the balance among parallel edges between each vertex pair. None of the previous algorithms are guaranteed to satisfy these balanced conditions simultaneously. To achieve these improvements, we propose a new recoloring procedure, which is based on a set of edge-disjoint alternating walks, while the existing algorithms are based on an Eulerian circuit or a single alternating walk. This new recoloring procedure makes it possible to reduce the time complexity of the algorithm.
DOI : 10.7155/jgaa.00213
Keywords: graph coloring, equitable edge coloring, algorithm 
@article{JGAA_2010_14_2_a12,
     author = {Akiyoshi Shioura and Mutsunori Yagiura},
     title = {A {Fast} {Algorithm} for {Computing} a {Nearly} {Equitable} {Edge} {Coloring} with {Balanced} {Conditions}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {391--407},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2010},
     doi = {10.7155/jgaa.00213},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00213/}
}
TY  - JOUR
AU  - Akiyoshi Shioura
AU  - Mutsunori Yagiura
TI  - A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions
JO  - Journal of Graph Algorithms and Applications
PY  - 2010
SP  - 391
EP  - 407
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00213/
DO  - 10.7155/jgaa.00213
LA  - en
ID  - JGAA_2010_14_2_a12
ER  - 
%0 Journal Article
%A Akiyoshi Shioura
%A Mutsunori Yagiura
%T A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions
%J Journal of Graph Algorithms and Applications
%D 2010
%P 391-407
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00213/
%R 10.7155/jgaa.00213
%G en
%F JGAA_2010_14_2_a12
Akiyoshi Shioura; Mutsunori Yagiura. A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions. Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 391-407. doi : 10.7155/jgaa.00213. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00213/

Cité par Sources :