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.