Seminár z teoretickej informatiky - Martin Nehéz (30.11.2018)

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

26. 11. 2018 13.23 hod.
Od: Rastislav Královič

Prednášajúci: Martin Nehéz

Názov: Analýza frekvenčnej distribúcie grafletov v riedkych náhodných grafoch

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

Abstrakt:
Graflety sú "malé" súvislé indukované podgrafy daného grafu. Metóda porovnávania sietí, založená na frekvenčnej štatistickej analýze grafletov, bola prvýkrát použitá v bioinformatike [Pržulj, Corneil, Jurišica, 2003].

Prednáška bude venovaná vysvetleniu uvedenej metódy a algoritmických problémov, ktoré s ňou súvisia. Ukážeme princíp, ako je možné vypočítať frekvencie grafletov analyticky v modeli náhodných grafov Erdosa a Rényiho (E-R model). Uvedené výsledky sa dajú použiť napr. pri odhade veľkosti súvislého komponentu (tzv. Giant component) v riedkych náhodných grafoch. Na záver budú spomenuté otvorené problémy a námety pre budúci výskum.

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