Journal article
A channel assignment problem for optical networks modelled by Cayley graphs
SM Zhou
THEORETICAL COMPUTER SCIENCE | ELSEVIER SCIENCE BV | Published : 2004
Abstract
A problem arising from a recent study of scalability of optical networks seeks to assign channels to the vertices of a network so that vertices distance 2 apart receive distinct channels. In this paper we introduce a general channel assignment scheme for Cayley graphs on abelian groups, and derive upper bounds for the minimum number of channels needed for such graphs. As application we give a systematic way of producing near-optimal channel assignments for connected graphs admitting a vertex-transitive abelian group of automorphisms. Hypercubes are examples of such graphs, and for them our near-optimal upper bound gives rise to the one obtained recently by Wan. © 2003 Elsevier B.V. All right..
View full abstract