Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00213
A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions
Vol. 14, no. 2, pp. 391-407, 2010. Regular paper.
Abstract 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.
|
Submitted: September 2009.
Accepted: October 2010.
Final: October 2010.
Published: November 2010.
Communicated by
Larse Arge
|
Journal Supporters
|