Problem bojanja grafova i njegove primjene u telekomunikacijama

Fofonjka, Anamarija (2014) Problem bojanja grafova i njegove primjene u telekomunikacijama. Diploma thesis, Faculty of Science > Department of Mathematics.

[img] PDF
Restricted to Registered users only
Language: Croatian

Download (571kB) | Request a copy
[img] Archive (dodatni materijali ("algoritam prilagodbe"))
Restricted to Registered users only
Language: Croatian

Download (7MB) | Request a copy

Abstract

Today’s fast lifestyle is forcing people to use technology. For many people, life is unimaginable without a mobile device. Mobile network is a very complex structure and needs to be well-configured as the number of people who use its services is increasing daily. This paper deals with the problem of mobile network optimization. At the beginning, we list the basic terms in order to define mathematical model of the problem. We conclude that problem resolution demands finding the optimal solution to the graph coloring problem with additional conditions and restrictions. The corresponding optimization problem belongs to the class of NP-hard problems, which roughly means that it is very challenging to resolve. Once the problem is clearly defined, we present several algorithms for solving it. The algorithm inspired by the work of our immune system is not suitable and it gives the worst results. Much better results are obtained using very good initial coloring and local search for solution improvement. The adaptation algorithm gives equally good results, but it is several times slower. After that, we determine optimal parameters for all algorithms and test them by coloring six graphs that represent part of Japanese mobile network. At the end of the paper we list possible improvements and conclusions.

Item Type: Thesis (Diploma thesis)
Supervisor: Manger, Robert
Date: 2014
Number of Pages: 51
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 02 Jun 2015 11:30
Last Modified: 02 Jun 2015 11:30
URI: http://digre.pmf.unizg.hr/id/eprint/3940

Actions (login required)

View Item View Item