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ů. 1 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ů. 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

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/176133

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-510370


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce