TY - GEN
T1 - A fast algorithm for computing a nearly equitable edge coloring with balanced conditions
AU - Shioura, Akiyoshi
AU - Yagiura, Mutsunori
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=76249132801&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=76249132801&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02882-3_13
DO - 10.1007/978-3-642-02882-3_13
M3 - Conference contribution
AN - SCOPUS:76249132801
SN - 3642028810
SN - 9783642028816
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 116
EP - 126
BT - Computing and Combinatorics - 15th Annual International Conference, COCOON 2009, Proceedings
T2 - 15th Annual International Conference on Computing and Combinatorics, COCOON 2009
Y2 - 13 July 2009 through 15 July 2009
ER -