Popredné vedecké pracoviská FMFI UK

Katedra informatiky

Vedúci pracovník: Prof. RNDr.Branislav Rovan, PhD.

Počet pracovníkov: 21 tvorivých, 16 interných doktorandov, 1 technik
Kontakt: Mlynská dolina, 842 48  Bratislava
tel. (02) 6542 6635 , fax: (02) 6542 7041
e-mail: rovan(at)fmph.uniba.sk

Špecializácia pracoviska:

  • rozpracovávanie teoretických základov informatiky skúmaním problémov v oblasti teórie zložitosti a algoritmov
  • štúdium modelov sekvenčných, paralelných a distribuovaných výpočtov  so zameraním na otázky sily paralelizmu
  • výskum teoretických aspektov analýzy algoritmov, s dôrazom na algoritmy pre efektívne využívanie paralelných počítačov a efektívnu komunikáciu v počítačových sieťach
  • skúmanie teoretických modelov komunikačných sietí, najmä otázky vzťahu štruktúry siete, množstva v nej uloženej informácie a zložitosti komunikácie skúmanie teoretických základov bezpečnosti počítačových systémov
  • výskum v oblasti topologickej teórie grafov s dôrazom na symetrické vnorenia na kompaktné povrchy  
  • výskum problému farbenia v kubických grafov

Najvýznamnejšie výsledky:

  • zavedenie nového modelu pre skúmanie sekvenčných a paralelných prepisovacích systémov (g-systémy)
  • dôkaz uzavretosti nedeterministických tried priestorovej zložitosti na komplement (ocenený Goedlovou cenou)
  • zavedenie nového modelu pre skúmanie vplyvu komunikácie na zložitosť výpočtov (alternujúce synchronizované stroje)
  • získanie nových dolných a horných odhadov pre komunikáciu v sieťach (kompaktné routovanie, broadcast)
  • získanie nových dolných pre komunikačnú zložitosť
  • konštrukcia tried grafov s úzkym spektrom  algoritmy na lokalizáciu chybného uzla siete
  • vyriešenie Coxterovho problému charakterizácie grafov vnoriteľných ako regulárna mapa na niektoré plochy
  • výsledky o regulárnych vnoreniach úplných bipartitných grafov
  • vypracovanie teórie redukcie snarkov a nájdenie súvisu s neabelovskými konečnými grupami
  • skúmanie súvisu medzi hranovými zafarbeniami kubických grafov a steinerovskými systémami trojíc viedlo k dokázaniu hypotézy D. Archdeacona, že každý bezmostový kubický graf má zafarbenie každým netriviálnym steinerovským systémom
  • vyvrátenie Silnej hypotézy o 5-toku sformulovanej B. Moharom.

Domáce granty:

  • VEGA 1/1477/94 Teória jazykov, automatov a algoritmov, 1994-1996
  • VEGA 1/4315/97 Teória zložitosti a algoritmov, 1997-1999  
  • VEGA 1/7155/20 Teória zložitosti a algoritmov, 2000 – 2002  
  • VEGA  Teória modelov, zložitosti a algoritmov, 2003 – 2005  
  • APVT-20-018902  Algoritmické a zložitostné aspekty globálnych sietí  
  • APVT 51-027604 „Problémy farbenia v teórii grafov“m(spolupráca s MÚ SAV), 2005-2007

Granty EU:

  • Cooperative Action IC 1000- pilotný výskumný projekt predchádzajuci program COST ”Algorithms for Future Technologies (ALTEC), 1992-1995
  • INCO - Copernicus IP960195, ALTEC – KIT - Algorithms for Future Technologies, 1998-1999

Medzinárodné granty:

  • Bilaterálna slovensko-francúzska spolupraca “Štefánik” - Problémy farbenia grafov – nové trendy v aplikáciách, 2004-2005  
  • Bilaterálna slovensko-slovinská spolupráca - Algebraické a topologické metódy v kombinatorických štruktúrach, 2006-2007

Zoznam najvýznamnejších vedeckých publikácií v rokoch 2000 – 2006

R. Kráľovič, P. Ružička, D. Štefankovič: The complexity of shortest path and dilation bounded interval routing, Theoretical Computer Science, 234 (1-2) (2000) pp. 85-107

R. Elsasser, R. Královič, B. Monien: Scalable Sparse Topologies With Smal Spectrum. In Proc. of the 18th International Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, 2001   pp. 218-229

R. Nedela and M. Škoviera, Cayley snarks and almost simple groups, Combinatorica, Vol 21, 2001, pp. 583—590

B. Rovan, M. Slašťan: Eliminating Communication by Parallel Rewriting. In Proc. of 5th International Conference on Development in Language Theory, Vienna, 2001, Lecture Notes in Computer Science 2295, Springer-Verlag, Berlin, pp. 369-378

P. Ďuriš, J. Hromkovič, S. Jukna, M. Sauerhoff, G. Schnitger: On Multipartition Communication Complexity. In STACS 2001, Lecture Notes in Computer Science, Springer-Verlag, 2001, pp. 206-217

P. Ďuriš, J. Maňuch: On the Computational Complexity of Infinite Words. In Proc. of MFCS'01, Lecture Notes in Computer Science 2136, 2001, pp. 328-337

R. Královič, B. Rovan, P. Ružička, D. Štefankovič: Efficient Deadlock-Free Multidimensional Interval Routing in Hypercube-like Networks, Computing and Informatics, Vol. 21, No. 3, 2002,  pp. 265-287

R. Královič, P.Ružička: Minimum Feedback Vertex Sets in Shuffle-Based Interconnection Networks Proc. of the 9th International Colloquium on Structural Information & Communication Complexity  (SIROCCO), Carleton Scientific, 2002

R. Nedela, M. Škoviera A. Zlatoš, Regular embeddings of complete bipartite graphs, Discrete Math, Vol. 258, 2002, pp. 379-381

F. Holroyd, M. Škoviera, Colouring of cubic graphs by Steiner triple systems,  J. Combinatorial Theory Ser. B 91 (2004), 57-66.  

M. Grannell, T. Griggs, M. Knor, M. Škoviera, A Steiner triple system which colors all cubic graphs, J. Graph Theory 46 (2004), 15-24.

P. Potočnik, R. Škrekovski, M. Škoviera, Nowhere-zero 3-flows in abelian Cayley Graphs, Discrete Math. 297 (2005), 119—127.

E. Máčajová, A. Raspaud, M. Škoviera, Abelian colourings of cubic graphs, Electron. Notes Discrete Math. 22 (2005), 333-339.

E. Máčajová, A. Raspaud, On the strong circular 5-flow conjecture, J. Graph Theory 52 (2005), 307-316.

E. Máčajová, M. Škoviera, Fano colourings of cubic graphs and the Fulkerson Conjecture, Theoret. Comp. Sci. 49 (2005), 112-20.

E. Máčajová, M. Škoviera,  Irreducible snarks of given order and cyclic connectivity, Discrete Math. 306 (2006), 779-791.

E. Máčajová, M. Škoviera, Hypohamiltonian snarks with cyclic connectivity 5 and 6, Electron. Notes Discrete Math. 24 (2006), 125-132.

M. Chladný, M. Škoviera, Decompositions of snarks into repeated dot-products, Electron. Notes Discrete Math. 24 (2006), 215-222.

H. Broersma, F.Fomin, R.Královič, G.Woeginger: Eliminating graphs by means of parallel knock-out schemes, Discrete Applied Mathematics (in press, available online, doi:10.1016/j.dam.2006.04.034 )

S. Dobrev, P. Flocchini, R. Královič, G. Prencipe, P. Ružička, N. Santoro: Optimal search for a black hole in common interconnection networks, Networks, 47 (2), p. 61-71,     

P. Flocchini, R. Královič, A. Roncato, P. Ružička, N. Santoro: On Time versus Size for Monotone Dynamic Monopolies in Reguar Topologies, Journal of Discrete Algorithms, 1

R. Elsässer, R. Královič, B. Monien: Sparse Topologies With Small Spectrum Size, Theoretical Computer Science 307, p. 549-565, Elsevier Science, 2003

R. Královič, P. Ružička: Minimum Feedback Vertex Sets in Shuffle-Based Interconnection Networks, Information Processing Letters 86, p. 191-196, Elsevier Science, 2003

S. Dobrev, R. Královič, R. Královič, N. Santoro: On Fractional Dynamic Faults with Threshold, LNCS 4056, Proc 13th International Colloquium on Structural Information and   

S. Dobrev, P. Flocchini, R. Královič, N. Santoro: Exploring an Unknown Graph to Locate a Black Hole Using Tokens, IFIP TCS 2006   S. Dobrev, R. Královič, N. Santoro, W. Shi: Black Hole Search in Asynchronous Rings Using Tokens, LNCS 3998, Proc. 6th Italian Conference on Algorithms and Complexity, CI 

R. Královič, R. Královič: On semi-perfect 1-factorizations, LNCS 3499, Proc 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO) 

R. Královič, R. Královič, P. Ružička: Broadcasting with many faulty links, Proc. 10th International Colloquium on Structural Information and Communication Complexity (SIR