An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem

An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem
复制标题

DOI：
--
复制
发表时间：
2004-05
期刊：
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
影响因子：
--
通讯作者：
X. Xie;Takao Ono;Shin-Ichi Nakano;T. Hirata
X. Xie;Takao Ono;Shin-Ichi Nakano;T. Hirata
中科院分区：
其他
文献类型：
--
作者：
X. Xie;Takao Ono;Shin-Ichi Nakano;T. Hirata

文献摘要

被引文献

相似文献

多重图的近均匀边染色是指与每个顶点关联的边在数量上均匀着色的染色。这个问题在O（kn 2）时间内解决，其中n和k分别是边和颜色的数量。运行时间为O（n2/k + n| V|）稍后。我们提出了一个更有效的算法，这个问题的运行时间为O（n2/k）。关键词：近均匀边染色，欧拉回路
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. key words: nearly equitable edge coloring, Euler circuit