We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Using Laplacian Eigenvalues and Eigenvectors in the Analysis of Frequency Assignment Problems.
- Authors
Van Den Heuvel, Jan; Snežana Pejić
- Abstract
A Frequency Assignment Problem (FAP) is the problem that arises when frequencies have to be assigned to a given set of transmitters so that spectrum is used efficiently and the interference between the transmitters is minimal. In this paper we see the frequency assignment problem as a generalised graph colouring problem, where transmitters are presented by vertices and interaction between two transmitters by a weighted edge. We generalise some properties of Laplacian matrices that hold for simple graphs. We investigate the use of Laplacian eigenvalues and eigenvectors as tools in the analysis of properties of a FAP and its generalised chromatic number (the so-called span).
- Subjects
ASSIGNMENT problems (Programming); NONLINEAR assignment problems; RADIO frequency; RADIO transmitter-receivers; LAPLACIAN operator; MATRICES (Mathematics); EIGENVALUES; OPERATIONS research
- Publication
Annals of Operations Research, 2001, Vol 107, Issue 1-4, p349
- ISSN
0254-5330
- Publication type
Article
- DOI
10.1023/A:1014927805247