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

Permalink: http://www.nusl.cz/ntk/nusl-510370


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses