Geodesic
An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem
Journal of Graph Algorithms and Applications, Tome 12 (2008) no. 4, pp. 383-399.

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

An edge coloring of a multigraph is nearly equitable if, among the edges incident to each vertex, the numbers of edges colored with any two colors differ by at most two. It has been proved that the problem of finding a nearly equitable edge coloring can be solved in O(m2/k) time, where m and k are the numbers of edges and given colors, respectively. In this paper, we present a recursive algorithm that runs in O(mn log(m/(kn) +1) ) time, where n is the number of vertices. This algorithm improves the best-known worst-case time complexity. When k=O(1), the time complexity of all known algorithms is O(m2), which implies that this time complexity remains to be the best for more than twenty years since 1982 when Hilton and de Werra gave a constructive proof for the existence of a nearly equitable edge coloring for any multigraph. Our result is the first that improves this time complexity when m/n grows to infinity; e.g., m = n θ for an arbitrary constant θ > 1. 
@article{JGAA_2008_12_4_a0,
     author = {Xuzhen Xie and Mutsunori Yagiura and Takao Ono and Tomio Hirata and Uri Zwick},
     title = {An {Efficient} {Algorithm} for the {Nearly} {Equitable} {Edge} {Coloring} {Problem}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {383--399},
     publisher = {mathdoc},
     volume = {12},
     number = {4},
     year = {2008},
     doi = {10.7155/jgaa.00171},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00171/}
}
TY  - JOUR
AU  - Xuzhen Xie
AU  - Mutsunori Yagiura
AU  - Takao Ono
AU  - Tomio Hirata
AU  - Uri Zwick
TI  - An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem
JO  - Journal of Graph Algorithms and Applications
PY  - 2008
SP  - 383
EP  - 399
VL  - 12
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00171/
DO  - 10.7155/jgaa.00171
LA  - en
ID  - JGAA_2008_12_4_a0
ER  - 
%0 Journal Article
%A Xuzhen Xie
%A Mutsunori Yagiura
%A Takao Ono
%A Tomio Hirata
%A Uri Zwick
%T An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem
%J Journal of Graph Algorithms and Applications
%D 2008
%P 383-399
%V 12
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00171/
%R 10.7155/jgaa.00171
%G en
%F JGAA_2008_12_4_a0
Xuzhen Xie; Mutsunori Yagiura; Takao Ono; Tomio Hirata; Uri Zwick. An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem. Journal of Graph Algorithms and Applications, Tome 12 (2008) no. 4, pp. 383-399. doi : 10.7155/jgaa.00171. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00171/

Cité par Sources :