Algoritmy pro specifické třídy grafů - NDMI077

• Anglický název: Algorithms for Specific Graph Classes
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Garant: doc. RNDr. Jiří Fiala, Ph.D.
• Vyučující: doc. RNDr. Jiří Fiala, Ph.D.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

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.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (04.05.2015)

angličtina

Special course for advanced undergraduate and graduate students devoted to algorithm design for restricted graph classes.

Poslední úprava: Macharová Dana, JUDr. (14.10.2008)

Literatura

čeština

Předmět v LS 2021/22 NENÍ VYUČOVÁN.

• 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.

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (20.12.2021)

angličtina

This lecture is NOT BEING TAUGHT in the summer term 2021/22.

• 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.

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (20.12.2021)

Sylabus

čeština

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) případně s danou reprezentací (průnikové grafy intervalů, kruhů a dalších geometrických objektů).

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (04.05.2015)

angličtina

In the course will be shown desing of effective algorithms for NP-hard problems on graphs of bounded treewidth. Some other graph classes (e.g. intersection graphs) will also be considered.

Poslední úprava: Macharová Dana, JUDr. (14.10.2008)