Seminár z teoretickej informatiky - Robert Lukoťka (2.12.2016)

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

---

Prednášajúci: Robert Lukoťka

Názov: Krátke cyklové pokrytia grafov

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

Abstrakt:
Nech G je bezmostový graf. Cyklové pokrytie grafu je kolekcia kružníc taká, že každá hrana sa nachádza v niektorej z kružníc. Dĺžka cyklového pokrytia je súčet dĺžok kružníc v cyklovom pokrytí. Problém nájdenia krátkeho cyklového pokrytia možno redukovať na váhované kubické grafy (pričom váha hrany reprezentuje jej dĺžku). Pre neváhované kubické grafy ukážeme, že každý bezmostový kubický graf má cyklové pokrytie dĺžky nanajvýš 1.6 m, kde m je počet hrán grafu. Dôkaz je konštruktívny a umožňuje vytvoriť 1.2-aproximačný algoritmus pre problém nájdenia najkratšieho kubického grafu. Použitými metódami zároveň ilustrujeme známe aproximačné algoritmy pre váhovaný prípad.

Podľa článku B. Candráková, R. Lukoťka: Short Cycle Covers on Cubic Graphs by Choosing a 2-Factor, SIAM Journal on Discrete Mathematics 30(4), 2086-2106 (2016) 

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

---