Original title:
Barvení grafů bez trojúhelníků na toru
Translated title:
Coloring triangle-free graphs on the torus
Authors:
Urmanov, Eldar ; Dvořák, Zdeněk (advisor) ; Šámal, Robert (referee) Document type: Bachelor's theses
Year:
2022
Language:
eng Abstract:
[eng][cze] Pekárek and Dvořák (2021) proposed a linear-time algorithm to decide 3-colorability of triangle-free graphs drawn on the torus. We implemented this algorithm efficiently and evaluated its performance on a natural class of graphs. Pekárek and Dvořák (2021) popsali algoritmus rozhodující 3-obarvitelnost grafu bez trojúhelníků nakreslených na toru v lineárním čase. Tato práce popisuje efektivní implementaci algoritmu a vyhodnocení jejího výkonu na přirozené tridě grafů. 1Pekárek and Dvořák (2021) popsali algoritmus rozhodující 3-obarvitelnost grafu bez trojúhelníků nakreslených na toru v lineárním čase. Tato práce popisuje efektivní implementaci algoritmu a vyhodnocení jejího výkonu na přirozené tridě grafů. Pekárek and Dvořák (2021) proposed a linear-time algorithm to decide 3-colorability of triangle-free graphs drawn on the torus. We implemented this algorithm efficiently and evaluated its performance on a natural class of graphs. 1
Keywords:
toroidal|graph|3-colorability|algorithm|implementation; toroidalni|graf|3-obarvitelnost|algoritmus|implementace
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/176133