Järjestetyt peitteettömät joukkoperheet verkonvärityksessä
Antti Karkinen · Aaltodoc (Aalto University) · 2021
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.