Seminár z teoretickej informatiky - Rastislav Královič (18.3.2016)

v piatok 18.3.2016 o 11:00 hod. v miestnosti M/213

16. 03. 2016 11.31 hod.
Od: Rastislav Královič

Prednášajúci: Rasťo Královič

Názov: Editovanie grafu na dve triedy

Termín: 18.3.2016, 11:00hod., M/213

Abstrakt:
Budeme skúmať zložitosť nasledovného problému: k danému grafu treba pridať a ubrať čo najmenej hrán, aby sme dostali jeden graf z triedy $C_1$ a jeden graf z triedy $C_2$. Včlánku [Ivan Kováč, Ivana Selečéniová, Monika Steinová , MFCS 2014] sa ukázalo, že špeciálny prípad, keď $C_1$ sú kliky a $C_2$ sú izolované vrcholy (t.j. máme pridať a ubrať čo najmenej hrán tak, aby sme dostali kliku a izolované vrcholy) je NP-úplný vo všeobecnosti (aj na bipartitných grafoch), ale pre planárne grafy existuje polynomiálny algoritmus. 6V našom článku zovšeobecňujeme tieto výsledky na FPT algoritmy pre rôzne verzie editovania na "hustý" a "riedky" graf.

Podľa článku: Michal Kotrbčík, Rastislav Královič and Sebastian Ordyniak. Edge-editing to a Dense and a Sparse Graph Class, LATIN 2016, to appear

web: http://kedrigern.dcs.fmph.uniba.sk/STI2/
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php