Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 368)
Detail práce
   Přihlásit přes CAS
Aproximace nezávislosti rovinných grafů
Název práce v češtině: Aproximace nezávislosti rovinných grafů
Název v anglickém jazyce: Approximation of independence number of planar graphs
Klíčová slova: rovinné grafy, nezávislá množina, aproximace
Klíčová slova anglicky: planar graphs, independent set, approximation
Akademický rok vypsání: 2016/2017
Typ práce: bakalářská práce
Jazyk práce: čeština
Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
Vedoucí / školitel: prof. Mgr. Zdeněk Dvořák, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 06.02.2017
Datum zadání: 06.02.2017
Datum potvrzení stud. oddělením: 14.02.2017
Datum a čas obhajoby: 06.09.2017 00:00
Datum odevzdání elektronické podoby:20.07.2017
Datum odevzdání tištěné podoby:21.07.2017
Datum proběhlé obhajoby: 06.09.2017
Oponenti: doc. RNDr. Jiří Fiala, Ph.D.
 
 
 
Zásady pro vypracování
Určit přesně velikost největší nezávislé množiny je NP-těžké i v rovinných grafech. Bakerová ale navrhla polynomiální aproximační schéma pro tento problém. Cílem práce je naimplementovat tento algoritmus a experimentálně ho srovnat s dalšími algoritmy pro určení velikosti největší nezávislé množiny.
Seznam odborné literatury
Baker, B. (1994), Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM, 41 (1): 153–180.
Fomin, F.V., Grandoni, F. and Kratsch, D., 2009. A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM (JACM), 56(5), #25.
 
Univerzita Karlova | Informační systém UK