Special course for advanced undergraduate and graduate students devoted to algorithm design for restricted graph classes.
Last update: Macharová Dana, JUDr. (14.10.2008)
Kurz zaměřený na návrh algoritmů pro specifické třídy grafů. Vhodné pro studenty mat. a inf. od 3.r. i pro
doktorandy (M a I).
Doporučeno absolvování předmětu Grafové minory a stromové rozklady.
Last update: Hladík Milan, prof. Mgr., Ph.D. (04.05.2015)
Literature -
Diestel, R.: Graph Theory, graduate texts in mathematics, vol. 173., Springer Verlag, May 1997.
Kloks, T. Treewidth: Computations and approximations, no. 842 in Lecture Notes in Computer Science, Springer Verlag, 1994.
Časopisecká literatura podle specifikace přednášejícího.
Last update: Fiala Jiří, doc. RNDr., Ph.D. (04.02.2025)
Diestel, R.: Graph Theory, graduate texts in mathematics, vol. 173., Springer Verlag, May 1997.
Kloks, T. Treewidth: Computations and approximations, no. 842 in Lecture Notes in Computer Science, Springer Verlag, 1994.
Časopisecká literatura podle specifikace přednášejícího.
Last update: Fiala Jiří, doc. RNDr., Ph.D. (04.02.2025)
Syllabus -
This course focuses on the design of efficient algorithms for specific classes of graphs, for problems that are NP-hard in general. Namely, for graphs of different widths (tree decompositions - Courcelle's theorem, clique decompositions), of bounded degrees (Luks' isomorphism test), or with a given representation (intersection graphs of intervals, circles and other geometric objects).
The course is taught in the summer semester once every two years (alternates with NDMI059 - Graph Minors and Tree Decompositions).
Last update: Fiala Jiří, doc. RNDr., Ph.D. (04.02.2025)
Kurz zaměřený na návrh efektivních algoritmů pro specifické třídy grafů, a to pro problémy, které jsou v obecnosti NP-těžké. Jmenovitě pro grafy různých šířek (stromové rozklady - Courcellova věta, klikové rozklady), omezených stupňů (Luksův test isomorfismu), případně s danou reprezentací (průnikové grafy intervalů, kruhů a dalších geometrických objektů).
Kurz je vyučován v letním semestru jednou za dva roky (alternuje s NDMI059 - Grafové minory a stromové rozklady).
Last update: Fiala Jiří, doc. RNDr., Ph.D. (04.02.2025)