Název: Aproximace nezávislosti rovinných grafů
Překlad názvu: Approximation of independence number of planar graphs
Autoři: Berg, Michal ; Dvořák, Zdeněk (vedoucí práce) ; Fiala, Jiří (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2017
Jazyk: cze
Abstrakt: [cze] [eng]
Problém nezávislé množiny je dobře známý NP-úplný problém, který je NP-úplný i pro rovinné grafy. Ale na rozdíl od obecných grafů, pro rovinné grafy existuje polynomiální aproximační schéma. Popíšeme přesný algoritmus pro hledání největší nezávislé množiny v rovinných grafech založený na dynamickém programování. Tento přesný algoritmus lze jednoduše upravit na polynomiální aproximační schéma. Obě jeho verze jsme implemen- tovali a otestovali. Při tom jsme používali několik generátorů náhodných rovinných grafů. Přesný algoritmus jsme experimentálně srovnávali s dalšími dvěma algoritmy. Aproximační algoritmus jsme srovnávali s jeho přesnou verzí a měřili skutečný aproximační poměr a také jeho časovou náročnost v porovnání s přesnou verzí. Zjistili jsme, že přesný algoritmus na zvolených grafech většinou dokončí výpočet rychleji než ostatní dva algoritmy. Také jsme zjistili, že aproximační verze má vzhledem k teoretickému minimu většinou lepší apro- ximační poměr s dobrou časovou složitostí. 1 The independent set problem is a well-known NP-complete problem, which is NP- complete even for planar graphs. But unlike general graphs, there exists an polynomial- time approximation scheme for planar graphs. We are going to describe an exact algorithm for maximum independent set problem in planar graphs based on dynamic programming. This algorithm can be easily modified to an polynomial-time approximation scheme. We implemented both versions of this algorithm and tested them. We used a few random planar graph generators for that. We compared the exact algorithm with another two algorithms. We compared the approximation algorithm with its exact version and measured its real approximation ratio and also its time complexity in comparison with the exact version. We discovered that the exact algorithm usually finishes the computation faster than the other two algorithms. We also discovered that the approximation version has a better approximation ratio compared to the theoretical minimum with good time complexity. 1
Klíčová slova: aproximace; nezávislá množina; rovinné grafy; approximation; independent set; planar graphs

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/90442

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


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