Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teórie grafov - Rastislav Královič (26.10.2017)

vo štvrtok 26.10.2017 o 9:50 hod. v miestnosti M/213


25. 10. 2017 08.28 hod.
Od: Martin Škoviera

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