Algorithmic and structural graph theory

• Thesis title in Czech: Algoritmická a strukturální teorie grafů
• Thesis title in English: Algorithmic and structural graph theory
• Academic year of topic announcement: 2011/2012
• Thesis type: dissertation
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: prof. RNDr. Daniel Kráľ, Ph.D., DSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 21.09.2011
• Date of assignment: 26.09.2011
• Confirmed by Study dept. on: 29.12.2011

Guidelines

Student se seznámí s výsledky o třídách grafů a s používanými postupy v oblasti návrhu algoritmů a datových struktur. Tyto poznatky využije k důkazu nových algoritmických metatvrzení a v dle potřeby doplní o důkazy nových strukturálních vlastností grafů ze studovaných tříd. Výsledky uváží i v obecnějším kontextu CSP a relačních struktur.

References

R. G. Downey, D. M. Thilikos: Confronting intractability via parameters, to appear in Computer Science Review.
H.-D. Ebbinghaus, J. Flum: Finite model theory, Springer, 2005.
J. Flum, M. Grohe: Parameterized complexity theory, Birkhäuser, 2006.
M. Grohe, S. Kreutzer: Methods for Algorithmic Meta Theorems, to appear in M. Grohe, J. Makowsky (eds.), Model theoretic methods in finite combinatorics, AMS Contemporary Mathematics Series.
R. Niedermeier: Invitation to fixed-parameter algorithms, Oxford University Press, 2006.