2024-04-19T13:01:17Z
https://nagoya.repo.nii.ac.jp/oai
oai:nagoya.repo.nii.ac.jp:00013169
2023-01-16T04:00:16Z
320:321:322
An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem
XIE, Xuzhen
41555
ONO, Takao
41556
NAKANO, Shin-ichi
41557
HIRATA, Tomio
41558
nearly equitable edge coloring
Euler circuit
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(kn^2) time, where n and k are the numbers of the edges and the colors, respectively. The running time was improved to be O(n^2/k + n|V|) later. We present a more efficient algorithm for this problem that runs in O(n^2/k) time.
journal article
Institute of Electronics, Information and Communication Engineers
2004-05-01
application/pdf
IEICE transactions on fundamentals of electronics, communications and computer sciences
5
E87-A
1029
1033
http://www.ieice.org/jpn/trans_online/index.html
http://hdl.handle.net/2237/15064
0916-8508
https://nagoya.repo.nii.ac.jp/record/13169/files/463.pdf
eng
http://www.ieice.org/jpn/trans_online/index.html
Copyright (C) 2004 IEICE