An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem

Xuzhen XIE  Takao ONO  Shin-ichi NAKANO  Tomio HIRATA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.5   pp.1029-1033
Publication Date: 2004/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
nearly equitable edge coloring,  Euler circuit,  

Full Text: PDF(157.9KB)
>>Buy this Article


Summary: 
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(kn2) time, where n and k are the numbers of the edges and the colors, respectively. The running time was improved to be O(n2/k + n|V|) later. We present a more efficient algorithm for this problem that runs in O(n2/k) time.