Algorithm for the cost edge-coloring of trees

Xiao Zhou; Takao Nishizeki

doi:10.1007/3-540-44679-6_32

Algorithm for the cost edge-coloring of trees

Xiao Zhou, Takao Nishizeki

INF - System Information Sciences

Tohoku University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

9 Citations (Scopus)

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Δ²) if n is the number of vertices and Δ is the maximum degree of T.

Original language	English
Title of host publication	Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings
Editors	Jie Wang
Publisher	Springer Verlag
Pages	288-297
Number of pages	10
ISBN (Print)	9783540424949
DOIs	https://doi.org/10.1007/3-540-44679-6_32
Publication status	Published - 2001
Event	7th Annual International Conference on Computing and Combinatorics, COCOON 2001 - Guilin, China Duration: 2001 Aug 20 → 2001 Aug 23

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2108
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th Annual International Conference on Computing and Combinatorics, COCOON 2001
Country/Territory	China
City	Guilin
Period	01/8/20 → 01/8/23

Access to Document

10.1007/3-540-44679-6_32

Cite this

Zhou, X., & Nishizeki, T. (2001). Algorithm for the cost edge-coloring of trees. In J. Wang (Ed.), Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings (pp. 288-297). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2108). Springer Verlag. https://doi.org/10.1007/3-540-44679-6_32

@inproceedings{2a93a27e661a402681e1744e52450961,

title = "Algorithm for the cost edge-coloring of trees",

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.",

author = "Xiao Zhou and Takao Nishizeki",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 7th Annual International Conference on Computing and Combinatorics, COCOON 2001 ; Conference date: 20-08-2001 Through 23-08-2001",

year = "2001",

doi = "10.1007/3-540-44679-6_32",

language = "English",

isbn = "9783540424949",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "288--297",

editor = "Jie Wang",

booktitle = "Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings",

address = "Germany",

}

Zhou, X & Nishizeki, T 2001, Algorithm for the cost edge-coloring of trees. in J Wang (ed.), Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2108, Springer Verlag, pp. 288-297, 7th Annual International Conference on Computing and Combinatorics, COCOON 2001, Guilin, China, 01/8/20. https://doi.org/10.1007/3-540-44679-6_32

Algorithm for the cost edge-coloring of trees. / Zhou, Xiao; Nishizeki, Takao.
Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. ed. / Jie Wang. Springer Verlag, 2001. p. 288-297 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2108).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Zhou X, Nishizeki T. Algorithm for the cost edge-coloring of trees. In Wang J, editor, Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. Springer Verlag. 2001. p. 288-297. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44679-6_32

Algorithm for the cost edge-coloring of trees

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this