Algorithm for the Cost Edge-Coloring of Trees |
| |
Authors: | Xiao Zhou Takao Nishizeki |
| |
Institution: | (1) Graduate School of Information Sciences, Tohoku University, Aoba-yama 05, Sendai, 980-8579, Japan |
| |
Abstract: | Let C be a set of colors, and let be a cost function which assigns a real number (c) to each color C in C. An edge-coloring of a graph G is to color all the edges of G so that any two adjacent edges are colored with different colors. In this paper we give an efficient algorithm to find an optimal edge-coloring of a given tree T, that is, an edge-coloring f of T such that the sum of costs (f(e)) of colors f(e) assigned to all edges e is minimum among all edge-colorings of T. The algorithm takes time O(n 2) if n is the number of vertices and is the maximum degree of T. |
| |
Keywords: | bipartite graph cost edge-coloring matching tree |
本文献已被 SpringerLink 等数据库收录! |
|