Ordered cover-free families in graph coloring

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Date
2021-08-23
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
29
Series
Abstract
Distributed computing is a subfield of theoretical computer science that studies distributed systems, where multiple components interact with one another in order to achieve some common goal. Distributed algorithms are used in many areas of distributed computing, such as telecommunications, scientific computing, and distributed information processing. One of the most fundamental graph problems is vertex coloring. In the extensively studied LOCAL model, Linial showed (1992) that cover-free families can be used to reduce the number of colors fast. In this thesis, I will give the reader a brief introduction to distributed algorithms, graph coloring, and related subjects. I will do a short survey on what is already known about cover-free families and define more constricted ordered cover-free families. Next, I show how these ordered cover-free families can be used to create a single-round color reduction algorithm. In this work, highly optimized SAT solvers were used to find cover-free families. SAT solvers are designed to solve Boolean satisfiability problems and in this thesis, I show one way to encode cover-free families as Boolean satisfiability problems. Utilizing the PySAT toolkit, I created a Python program that was run on a virtual machine service for a few months. This dataset, containing both unordered and ordered cover-free families, was used to compare the runtimes of single-round color reduction algorithms. In paths and circles, the algorithm based on ordered cover-free families is slower than already known best color reduction algorithms, but it is still faster than earlier algorithms using unordered cover-free families.

Hajautettu laskenta on teoreettisen tietojenkäsittelyn osa-alue, joka tutkii hajautettuja järjestelmiä. Näissä järjestelmissä useat osatekijät vuorovaikuttavat keskenään saavuttaakseen yhteisen päämäärän. Hajautettuja algoritmeja käytetään laajasti hajautetussa laskennassa, kuten telekommunikoinnissa, tieteellisessä laskennassa ja hajautetussa tiedon käsittelyssä. Yksi perustavanlaatuinen verkko-ongelma on verkon värittäminen. Linial näytti (1992), että laajasti tutkitussa LOCAL mallissa, voidaan käyttää peitteettömiä joukkoperheitä nopeassa värinvähennyksessä. Tässä diplomityössä annan lukijalle lyhyen johdannon hajautettuihin algoritmeihin, verkon väritykseen ja muihin aiheeseen liittyviin käsitteisiin. Teen pienen kirjallisuuskatsauksen siitä, mitä tiedämme peitteettömistä joukkoperheistä. Määrittelen rajatumman järjestetyn peitteettömän joukkoperheen ja näytän, miten niitä voidaan käyttää yhden vuoron värinvähennys algoritmissa. Työssä käytettiin erittäin optimoituja SAT ratkojia löytämään peitteettömiä joukkoperheitä. SAT ratkojat on suunniteltu ratkaisemaan Boolen algebran ongelmia ja tässä diplomityössä näytän yhden tavan koodata peitteettömiä joukkoperheitä Boolen algebran lausekkeiksi. Hyödyntäen PySAT-moduulia tein Python ohjelman, mitä ajettiin virtuaalikone palvelussa muutaman kuukauden ajan. Luotua tietokantaa, sisältäen järjestämättömiä ja järjestettyjä peitteettömiä joukkoperheitä, käytettiin vertaamaan yhden vuoron värinvähennys algoritmien nopeuksia. Poluissa ja kehissä järjestettyyn peitteettömään joukkoperheeseen pohjautuva algoritmi on hitaampi kuin ennestään tiedetyt parhaat algoritmit, mutta se on nopeampi kuin aikaisemmin käytetty järjestämätöntä joukkoperhettä käyttävä algoritmi.
Description
Supervisor
Suomela, Jukka
Thesis advisor
Hirvonen, Juho
Keywords
distributed algorithms, graph theory, graph coloring, cover-free family, hajautettu algoritmi, peitteetön joukko
Other note
Citation