Aproximace nezávislosti rovinných grafů

• Thesis title in Czech: Aproximace nezávislosti rovinných grafů
• Thesis title in English: Approximation of independence number of planar graphs
• Key words: rovinné grafy, nezávislá množina, aproximace
• English key words: planar graphs, independent set, approximation
• Academic year of topic announcement: 2016/2017
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 06.02.2017
• Date of assignment: 06.02.2017
• Confirmed by Study dept. on: 14.02.2017
• Date and time of defence: 06.09.2017 00:00
• Date of electronic submission: 20.07.2017
• Date of submission of printed version: 21.07.2017
• Date of proceeded defence: 06.09.2017
• Opponents: doc. RNDr. Jiří Fiala, Ph.D.

Guidelines

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.

References

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.