3rd workshop of the Center of Modern Computer Science
3. seminář Centra moderní informatiky
The third workshop of the Center of Modern Computer Science will take place on Friday June 7, 2013.
Centrum moderní informatiky zve na třetí seminář, který se koná v rámci konference STTI 2013. Přednášky juniorů centra se konají v průběhu programu v pátek 7. 6. 2013 v posluchárně S5 v budově MFF UK na Malé štraně.
| 9:00 | Jan Kynčl: Kolika způsoby lze jednoduše nakreslit graf? |
|---|---|
| 10:30 | Josef Cibulka: O množinách bodů bez pětiděr |
| 15:15 | Zdeněk Dvořák: Metaalgoritmy a dynamické datové struktury |
Abstracts
Jan Kynčl: Kolika způsoby lze jednoduše nakreslit graf?
Jednoduchý topologický graf je nakreslení grafu v rovině, kde každé dvě hrany mají nejvýše jeden společný bod (a to buď vrchol nebo křížení) a žádné tři hrany se nekříží ve stejném bodě. Topologické grafy G a H jsou izomorfní, pokud H lze získat z G homeomorfismem sféry, a slabě izomorfní, pokud G i H mají stejnou množinu dvojic křížících se hran. Dokážeme, že pro každý graf G s n vrcholy a m hranami, který nemá izolované vrcholy, počet tříd slabého izomorfismu jednoduchých topologických grafů, které realizují G, je nejvýše 2O(n2log(m/n)) a nejvýše 2O(mn1/2log n) pro m<n3/2.
Josef Cibulka: O množinách bodů bez pětiděr
(příspěvek obsahuje výsledky společné práce s J. Kynčlem a P. Valtrem)
Množina S bodů v rovině obsahuje k-díru, pokud v ní existuje k-tice bodů tvořící vrcholy konvexního k-úhelníka, v němž neleží žádné další body množiny S. Příkladem množiny bez pětidíry je čtvercová mřížka. Viditelnostn í graf množiny S je graf, jehož vrcholy jsou body množiny S a dvojice vrcholů je spojena hranou právě tehdy, když jejich spojnice neobsahuje žádný bod množiny S. Zkonstruujeme rovinnou množinu bodů bez pětidíry s libovolně velkou klikou ve viditelnostním grafu, čímž odpovíme na otázku položenou D. Woodem.
Zdeněk Dvořák: Metaalgoritmy a dynamické datové struktury
(příspěvek obsahuje výsledky společné práce s V. Tůmou a M. Kupcem)
Slavný Courcelleho výsledek říká, že každý problém vyjádřitelný v monadické logice druhého řádu (MSOL) lze v lineárním čase rozhodovat pro grafy omezené stromové šířky. Dvořák, Kráľ a Thomas (FOCS'10) ukázali, že problémy vyjádřitelné v logice prvního řádu (FO) lze v lineárním čase rozhodovat pro grafy s omezenou expanzí. Zabýváme se dynamickou verzí těchto problémů, pro kterou jsme získali následující částečné výsledky: dynamickou datovou strukturu pro rozhodov ání MSOL pro grafy omezené stromové hloubky, a dynamickou datovou strukturu pro rozhodování existenciální FO pro grafy s omezenou expanzí.
