Algorithm for the Cost Edge-Coloring of Trees

Xiao Zhou () and Takao Nishizeki ()
Additional contact information
Xiao Zhou: Tohoku University
Takao Nishizeki: Tohoku University

Journal of Combinatorial Optimization, 2004, vol. 8, issue 1, No 7, 97-108

Abstract: 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 (search for similar items in EconPapers)
Date: 2004
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/B:JOCO.0000021940.40066.0c Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:8:y:2004:i:1:d:10.1023_b:joco.0000021940.40066.0c

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/B:JOCO.0000021940.40066.0c

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().