Vis enkel innførsel

dc.contributor.authorWang, Shuangeng
dc.date.accessioned2008-11-10T13:51:57Z
dc.date.available2008-11-10T13:51:57Z
dc.date.issued2008-11-10eng
dc.date.submitted2007-11-20eng
dc.identifier.urihttps://hdl.handle.net/1956/2896
dc.description.abstractMany 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.en_US
dc.format.extent458389 byteseng
dc.format.mimetypeapplication/pdfeng
dc.language.isoengeng
dc.publisherThe University of Bergenen_US
dc.titleSelf-stabilizing algorithms for the distance-k coloring problemen_US
dc.typeMaster thesis
dc.rights.holderThe authoren_US
dc.rights.holderCopyright the author. All rights reserveden_US
dc.description.degreeMaster i Informatikken_US
dc.description.localcodeMAMN-INF
dc.description.localcodeINFL
dc.subject.nus759906eng
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420nob
fs.subjectcodeINFL


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel