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 |

1) Download Document PDF |

Open access Restricted Private