Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/4967
Title: The frequency assignment problem
Authors: Koller, Angela Erika
Keywords: Domination analysis;Outerplanar graphs;Polynomial time algorithm;Constraint matrix problem;One-close-neighbour problems
Issue Date: 2004
Publisher: Brunel University, School of Information Systems, Computing and Mathematics
Abstract: This thesis examines a wide collection of frequency assignment problems. One of the largest topics in this thesis is that of L(2,1)-labellings of outerplanar graphs. The main result in this topic is the fact that there exists a polynomial time algorithm to determine the minimum L(2,1)-span for an outerplanar graph. This result generalises the analogous result for trees, solves a stated open problem and complements the fact that the problem is NP-complete for planar graphs. We furthermore give best possible bounds on the minimum L(2,1)-span and the cyclic-L(2,1)-span in outerplanar graphs, when the maximum degree is at least eight. We also give polynomial time algorithms for solving the standard constraint matrix problem for several classes of graphs, such as chains of triangles, the wheel and a larger class of graphs containing the wheel. We furthermore introduce the concept of one-close-neighbour problems, which have some practical applications. We prove optimal results for bipartite graphs, odd cycles and complete multipartite graphs. Finally we evaluate different algorithms for the frequency assignment problem, using domination analysis. We compute bounds for the domination number of some heuristics for both the fixed spectrum version of the frequency assignment problem and the minimum span frequency assignment problem. Our results show that the standard greedy algorithm does not perform well, compared to some slightly more advanced algorithms, which is what we would expect. In this thesis we furthermore give some background and motivation for the topics being investigated, as well as mentioning several open problems.
Description: This thesis was submitted for the degree of Doctor of Philosophy and awarded by Brunel University.
URI: http://bura.brunel.ac.uk/handle/2438/4967
Appears in Collections:Dept of Mathematics Theses
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
FulltextThesis.pdf6.22 MBAdobe PDFView/Open


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