Buscar

 

RI UFLA (Universidade Federal de Lavras) >
Revistas UFLA >
Infocomp >

Please use this identifier to cite or link to this item: http://repositorio.ufla.br/jspui/handle/1/10056

Title: Algorithms for finding generalized coloring of trees
???metadata.dc.creator???: Awal, Tanveer
Mahbubuzzaman, M.
Kashem, MD. Abul
Keywords: Algorithm
Chordal graph
Chromatic number
Edge coloring
Vertex coloring
Graph
Tree
Algoritmo
Número cromático
Coloração de arestas
Coloração de vértices
Gráfico
Árvore
Publisher: Editora da UFLA
???metadata.dc.date???: 1-Mar-2011
Citation: AWAL, T.; MAHBUBUZZAMAN, M.; KASHEM, M. A. Algorithms for finding generalized coloring of trees. INFOCOMP: Journal of Computer Science, Lavras, v. 7, n. 1, p. 79-85, Mar. 2008.
Other Identifiers: http://www.dcc.ufla.br/infocomp/index.php/INFOCOMP/article/view/326
Description: Let � be a positive integer, and � be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an �-vertex-coloring of �, is an assignment of colors to the vertices in such a way that any two vertices � and � get different colors if the distance between � and � in � is at most �. A coloring is optimal if it uses minimum number of distinct colors. The �-vertex-coloring problem is to find an optimal �-vertex-coloring of a graph �. In this paper we present an ���� � ������ time algorithm to find an �-vertex-coloring of a tree � , where � is the maximum degree of � . The algorithm takes ����� time if both � and � are bounded integers. We compute the upper bound of colors to be � � ������������� ����� . We also present an ���� � ������ time algorithm for solving the �-edge-coloring problem of trees. If both � and � are bounded integers, this algorithm also takes ����� time.
???metadata.dc.language???: eng
Appears in Collections:Infocomp

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


View Statistics

 


DSpace Software Copyright © 2002-2010  Duraspace - Feedback