Algebraic graph theory in the analysis of frequency assignment problems

Pejić, Snežana (2008) Algebraic graph theory in the analysis of frequency assignment problems. PhD thesis, London School of Economics and Political Science.

Preview

PDF Download (13MB) | Preview

Abstract

Frequency Assignment Problems (FAPs) arise when transmitters need to be allocated frequencies with the aim of minimizing interference, whilst maintaining an efficient use of the radio spectrum. In this thesis FAPs are seen as generalised graph colouring problems, where transmitters are represented by vertices, and their interactions by weighted edges. Solving FAPs often relies on known structural properties to facilitate algorithms. When no structural information is available explicitly, obtaining it from numerical data is difficult. This lack of structural information is a key underlying motivation for the research work in this thesis. If there are TV transmitters to be assigned, we assume as given an N x N "influence matrix" W with entries Wij representing influence between transmitters i and j. From this matrix we derive the Laplacian matrix L = D—W, where D is a diagonal matrix whose entries da are the sum of all influences working in transmitter i. The focus of this thesis is the study of mathematical properties of the matrix L. We généralisé certain properties of the Laplacian eigenvalues and eigenvectors that hold for simple graphs. We also observe and discuss changes in the shape of the Laplacian eigenvalue spectrum due to modifications of a FAP. We include a number of computational experiments and generated simulated examples of FAPs for which we explicitly calculate eigenvalues and eigenvectors in order to test the developed theoretical results. We find that the Laplacians prove useful in identifying certain types of problems, providing structured approach to reducing the original FAP to smaller size subproblems, hence assisting existing heuristic algorithms for solving frequency assignments. In that sense we conclude that analysis of the Laplacians is a useful tool for better understanding of FAPs.

Item Type:	Thesis (PhD)
Additional Information:	© 2008 Snežana Pejić
Library of Congress subject classification:	Q Science > QA Mathematics
Sets:	Departments > Mathematics Collections > LSE History of Thought theses
Supervisor:	van den Heuvel, Jan
URI:	http://etheses.lse.ac.uk/id/eprint/129

Actions (login required)

Record administration - authorised staff only