An edge coloring is an assignment of colors to the edges of a graph so that no two edges with a common vertex have the same color. We show that, given an undirected tree T with n vertices, a minimum edge coloring of T can be determined in O( the square root of n ) time on a the square root of n ×the square root of n mesh-connected computer(MCC) by a novel technique which decomposes the tree into disjoint chains and then assigns the edge colors in each chain properly. The time complexity is optimal on MCC within constant factor.
展开▼
