TITLE: Permutation Routing in All-Optical Networks
AUTHORS: Weifa Liang, George Havas and Xiaojun Shen
CITATION: Technical Report 436, Department of Computer Science
and Electrical Engineering, The University of Queensland (1998)
ABSTRACT: We study permutation routing techniques for all-optical
networks. In these networks, messages travel in optical form and
switching is performed directly on the optical signal. By using
different wavelengths, several messages may use the same fiber-optic
link concurrently. However, messages assigned the same wavelength must
use disjoint paths, or else be routed in separate rounds.
First we present some lower bounds on the number of wavelengths needed
for implementing any permutation on an all-optical network in terms of
bisection and edge-connectivity of the network. We propose an algorithm
for implementing any permutation in a directed symmetric
network in one round with O(n/l) wavelengths on the wavelength
non-conversion model, where n is the number of nodes and l is
the edge connectivity of the network.
Then we study permutation routing on product networks which are defined as
a direct product of two networks. Product networks are important because
many well known commercial networks such as hypercubes, meshes, tori, etc,
are product networks. For product networks, we obtain a lower bound on
the number of wavelengths needed for implementing any permutation, and
present permutation routing algorithms for the wavelength non-conversion
and conversion models, respectively.
Finally we investigate permutation routing on cube-connected-cycles networks. For such networks with constant degree three we show that the number of wavelengths needed for implementing any permutation in one round is 2 log n , which improves on a previously known general result for bounded degree graphs by a factor of O(log^3 n) for this special case.
TITLE: Decomposition properties of sub-linearised polynomials
AUTHORS: Robert S. Coulter, George Havas and Marie Henderson
CITATION: Technical Report 27, Centre for Discrete Mathematics and
Computing, School of Information Technology and Electrical Engineering,
The University of Queensland (2002)
ABSTRACT: Previously it has been shown that there is a direct
relationship between linearised and sub-linearised polynomials over a
finite field. By exploiting this relationship we give a formula for
the number of indecomposable sub-linearised polynomials of given degree.
Also we note that these two classes of polynomials satisfy a theorem of
Ritt concerning complete decompositions into indecomposables.