Algebraic graph theory in the analysis of frequency assignment problems

مرکز و کتابخانه مطالعات اسلامی به زبان های اروپایی

منو

" Algebraic graph theory in the analysis of frequency assignment problems "
Pejić, Snežana

Document Type	:	Latin Dissertation
Record Number	:	1098471
Doc. No	:	TLets543143
Main Entry	:	Pejić, Snežana
Title & Author	:	Algebraic graph theory in the analysis of frequency assignment problems\ Pejić, Snežana
College	:	London School of Economics and Political Science (LSE)
Date	:	2008
student score	:	2008
Degree	:	Ph.D.
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 généralisé 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.
Subject	:	QA Mathematics
Added Entry	:	London School of Economics and Political Science (LSE)