PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Bertossi A. A., Pinotti M. C., Rizzi R. Channel assignment on strongly-simplicial graphs. In: IPDPS 2003 - 17th International Parallel and Distributed Processing Symposium (Nice, France, 22-26 April 2003). Proceedings, IEEE, 2003.
 
 
Abstract
(English)
Given a vector ( 1; 2; : : : ; t) of non increasing pos- itive integers, and an undirected graph G = (V;E), an L( 1; 2; : : : ; t)-coloring of G is a function f from the vertex set V to a set of nonnegative integers such that jf(u) -- f(v)j i, if d(u; v) = i; 1 i t; where d(u; v) is the distance (i.e. the minimum num- ber of edges) between the vertices u and v. This paper presents e cient algorithms for nding opti- mal L(1; : : : ; 1)-colorings of trees and interval graphs. Moreover, e cient algorithms are also provided for nding approximate L( 1; 1; : : : ; 1)-colorings of trees and interval graphs, as well as approximate L( 1; 2)- colorings of unit interval graphs
DOI: 10.1109/IPDPS.2003.1213408
Subject Distributed Systems
C.2.4 Distributed Systems


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional