[Translate to English:] Seminár z teórie grafov - Rastislav Královič (26.10.2017)

[Translate to English:] vo štvrtok 26.10.2017 o 9:50 hod. v miestnosti M/213

06. 11. 2017 12.56 hod.
By: Martin Škoviera

[Translate to English:] Prednášajúci: Rastislav Královič

Názov: Editovanie grafu na dve triedy

Termín: 26.10.2017, 9:50 hod., M/213

Abstrakt:
V prednáške nás bude zaujímať výpočtová zložitosť nasledujúceho problému, parametrizovaného dvoma triedami grafov G1, G2: pre daný graf G treba nájsť minimálny počet operácií vymazanie hrany / pridanie hrany tak, aby sme získali graf pozostávajúci z dizjunktného zjednotenia nejakého grafu z G1 a nejakého grafu z G2. Najprv ukážeme, že pre špeciálny prípad, keď G1 je trieda úplných grafov a G2 trieda grafov bez hrán je problém NP-ťažký, aj keď vstupný graf obmedzíme na triedu bipartitných grafov. Naopak, pre triedu planárnych grafov je polynomiálne riešiteľný. Ďalej spomenieme zovšeobecnenia pre editovanie na triedu "hustých" a "riedkych" grafov a budeme skúmať ich parametrizovanú zložitosť.