Fakulta Prírodných vied UMB


Grafové algoritmy a ich aplikácie

Informácie o projekte

Zadávateľ:

Vedecká grantová agentúra MŠ SR

 

Číslo projektu:VEGA 1/0150/14
Doba riešenia projektu:1. Január 2014 - 31. December 2016
Vedúci projektu FPV:prof. RNDr. Roman Nedela, DrSc.
Spoluriešitelia:

Ján Karabáš
Pavel Hrnčiar
Gabriela Monoszová
Michal Vagač

Zahraničný projekt:nie

Cieľom projektu je na jednej strane, preskúmať možnosti využitia výpočtovej techniky na výpočet vybraných vlastností grafov, na druhej strane odvodiť teoretické výsledky, ktoré umožnia zrýchliť známe algoritmy, respektíve dokázať výsledky týkajúce sa ich zložitosti. Zameriame sa najmä na štúdium nasledovných vlastností a invariantov: decyklačné číslo grafu, 3-ofarbiteľnosť (sub)kubických grafov, celulárne vnorenia kubických grafov do plôch malých rodov, rôzne invarianty snarkov, existencia k-tokov na signovaných (sub)kubických grafoch, hľadanie minimálnych excentricitových postupností grafov. Pokrok vo vývoji hardvéru a softvéru však umožňuje vykonať výpočet týchto invariantov v reálnom čase pre relatívne veľké grafy. Našim partikulárnym cieľom je nájsť hranice možností vo vyššie uvedenom zmysle.


Fakulta prírodných vied, Univerzita Mateja Bela