TY - GEN

T1 - Algorithm for the cost edge-coloring of trees

AU - Zhou, Xiao

AU - Nishizeki, Takao

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=23044529941&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23044529941&partnerID=8YFLogxK

U2 - 10.1007/3-540-44679-6_32

DO - 10.1007/3-540-44679-6_32

M3 - Conference contribution

AN - SCOPUS:23044529941

SN - 9783540424949

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 288

EP - 297

BT - Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings

A2 - Wang, Jie

PB - Springer Verlag

T2 - 7th Annual International Conference on Computing and Combinatorics, COCOON 2001

Y2 - 20 August 2001 through 23 August 2001

ER -