• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • View Item
  •   Home
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Self-stabilizing algorithms for the distance-k coloring problem

Wang, Shuang
Master thesis
Thumbnail
View/Open
42178762.pdf (447.6Kb)
URI
https://hdl.handle.net/1956/2896
Date
2008-11-10
Metadata
Show full item record
Collections
  • Department of Informatics [542]
Abstract
Many problems of practical interest can be modeled as coloring problems. For example, when you are making a phone call using a mobile phone, it needs to transform the voice signal into an electronic wireless signal. Eachsuch signal requires a specific frequency. If two mobile phones close to each other are using the same frequency they could interfere with each other and disrupt the signals. If we assign colors to the different frequencies it is easyto see that a coloring of the phones where phones close to each other receivedifferent colors solves the frequency assignment problem.The coloring problem can easily be generalized so that one requires that units (or phones) within a certain closeness of each other have to receive different colors. One such generalization is the k-coloring problem where weview the units as being connected in a graph and where units within distance k, for some k > 0 must have different colors.In my thesis I investigate self-stabilizing algorithms to solve the distance-k coloring problem. The reason for using a self-stabilizing algorithm is becauseit is an attractive approach when dealing with fault tolerance in distributedsystems. It provides a way to recover from faults without the costand inconvenience of human intervention: after a fault is diagnosed, onesimply has to repair the faulty components, and the system, by itself, will return to a good global state within a relatively shortamount of time.In my work I investigate how existing self-stabilizing algorithms forproviding distance-k knowledge in general networks can be combined withcoloring algorithms to produce a self-stabilizing k-coloring algorithm. This approach is feasible but will require excessiveamounts of memory. Thus I design a distance-2 coloring algorithm that only requires five variables stored in each node. This distance-2 coloring algorithmcan only guarantee to solve the distance-2 coloring problem,but both the number of different colors and the value of the highestcolor could be high. We therefore give an improved distance-2 coloringalgorithm that limits the number of colors. This algorithmrequires eight variables stored in each node.
Publisher
The University of Bergen
Copyright
The author
Copyright the author. All rights reserved

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit