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 edgecoloring 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 edgecoloring of a given tree T, that is, an edgecoloring f of T such that the sum of costs ω(f(e)) of colors f(e) assigned to all edges e is minimum among all edgecolorings of T. The algorithm takes time O(nΔ2) if n is the number of vertices and Δ is the maximum degree of T.

Year  DOI  Venue 

2004  10.1007/3540446796_32  J. Comb. Optim. 
Keywords  Field  DocType 
bipartite graph,cost edgecoloring,matching,tree  Discrete mathematics,Edge coloring,Graph,Combinatorics,Colored,Tree (graph theory),Vertex (geometry),Bipartite graph,Algorithm,Degree (graph theory),Real number,Mathematics  Journal 
Volume  Issue  ISSN 
8  1  13826905 
ISBN  Citations  PageRank 
3540424946  8  0.65 
References  Authors  
13  2 
Name  Order  Citations  PageRank 

Xiao Zhou  1  325  43.69 
Takao Nishizeki  2  1771  267.08 