عنوان
پدید آورنده
موضوع
رده
کتابخانه
محل استقرار
شماره کتابشناسی ملی
شماره
TLets543143
عنوان و نام پديدآور
عنوان اصلي
Algebraic graph theory in the analysis of frequency assignment problems
نام عام مواد
[Thesis]
نام نخستين پديدآور
Pejić, Snežana
وضعیت نشر و پخش و غیره
نام ناشر، پخش کننده و غيره
London School of Economics and Political Science (LSE)
تاریخ نشرو بخش و غیره
2008
یادداشتهای مربوط به پایان نامه ها
جزئيات پايان نامه و نوع درجه آن
Ph.D.
کسي که مدرک را اعطا کرده
London School of Economics and Political Science (LSE)
امتياز متن
2008
یادداشتهای مربوط به خلاصه یا چکیده
متن يادداشت
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.
موضوع (اسم عام یاعبارت اسمی عام)
موضوع مستند نشده
QA Mathematics
نام شخص به منزله سر شناسه - (مسئولیت معنوی درجه اول )
مستند نام اشخاص تاييد نشده
Pejić, Snežana
شناسه افزوده (تنالگان)
مستند نام تنالگان تاييد نشده
London School of Economics and Political Science (LSE)
دسترسی و محل الکترونیکی
نام الکترونيکي
مطالعه متن کتاب وضعیت انتشار
فرمت انتشار
p
اطلاعات رکورد کتابشناسی
نوع ماده
[Thesis]
کد کاربرگه
276903
اطلاعات دسترسی رکورد
سطح دسترسي
a
تكميل شده
Y
