Název:
Barvení grafů bez trojúhelníků na toru
Překlad názvu:
Coloring triangle-free graphs on the torus
Autoři:
Urmanov, Eldar ; Dvořák, Zdeněk (vedoucí práce) ; Šámal, Robert (oponent) Typ dokumentu: Bakalářské práce
Rok:
2022
Jazyk:
eng
Abstrakt: [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
Klíčová slova:
toroidalni|graf|3-obarvitelnost|algoritmus|implementace; toroidal|graph|3-colorability|algorithm|implementation