Výskumné skupiny
Modely výpočtov, zložitosť, algoritmy
V oblasti modelov výpočtov a zložitosti sa v posledných rokoch skúma najmä vplyv prídavnej informácie na zložitosť riešenia problémov, ako aj problematika paralelných gramatík a Turingových strojov. Boli tiež vyvinuté a implementované algoritmy na transformáciu XML dokumentov a vykresľovanie grafickej reprezentácie štrukturovaných dát. Ďalšou oblasťou záujmu sú techniky vyučovania algoritmov pre stredoškolských aj vysokoškolských študentov.
Členovia skupiny:
František Ďuriš, Pavol Ďuriš, Michal Forišek, Jana Katreniaková, Ivan Kováč, Rastislav Královič, Pavel Labath, Dana Pardubská, Branislav Rovan, Richard Štefanec, Marek Zeman
Vybrané publikácie:
- Michal Forišek, Monika Steinová. Explaining Algorithms Using Metaphors. Springer, 2013.
- Pavol Ďuriš. On Computational Power of Partially Blind Automata. Journal of Applied Mathematics, Statistics and Informatics 2012.
- Stefan Dobrev, Rastislav Královič, Richard Královič. Independent Set with Advice: The Impact of Graph Knowledge. WAOA 2012.
- Juraj Hromkovič, Rastislav Královič, Richard Královič, Richard Štefanec. Determinism vs. Nondeterminism for Two-Way Automata. DLT 2012.
- Michal Forišek, Lucia Keller, Monika Steinová. Advice complexity of online coloring for paths. LATA 2012.
- Michal Forišek, Monika Steinová. Metaphors and analogies for teaching algorithms. SIGCSE 2012.
- Jiří Dokulil, Jana Katreniaková. Boundary labeling of graph edges using colors. IV 2012.
- Pavel Labath. XSLT streamability analysis with recursive schemas. RCIS 2012.
- Viliam Geffert, Dana Pardubská. Unary Coded NP-Complete Languages in ASPACE (log log n). DLT 2012.
- Dana Pardubská, Martin Plátek, Friedrich Otto. Parallel communicating grammar systems with regular control and skeleton preserving FRR automata. Theoretical Computer Science 2011.
- Tomáš Kulich. Dynamic monopolies with randomized starting configuration. Theoretical Computer Science 2011.
- Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič. On the advice complexity of the k-server problem. ICALP 2011.
- Miroslav Čermák, Jiří Dokulil, Jana Katreniaková. Edge routing and bundling for graphs with fixed node positions. IV 2011.
- Pavel Labath, Branislav Rovan. Simplifying DPDA using supplementary information. LATA 2011.
Kryptológia a informačná bezpečnosť
Hlavné oblasti záujmu sú efektívne a dokázateľne bezpečné konštrukcie kryptografických prvkov, vzťahy a analýza vlastností hašovacích funkcií a bezpečnosť elektronického prostredia (operačné systémy, identifikácia škodlivého kódu a podobne).
Členovia skupiny:
Jaroslav Janáček, Marika Mitrengová, Daniel Olejár, Richard Ostertág, Michal Rjaško, Martin Stanek
Vybrané publikácie:
- Martin Stanek. Attacking scrambled Burrows-Wheeler transform. Infocommunications Journal 2012.
- Michal Rjaško, Martin Stanek. Attacking M&M Collective Signature Scheme. Fundamenta Informaticae 2012.
- Martin Stanek. A Note on Security Protocol for Multicast Communications. International Journal of Network Security 2012.
- Peter Gaži, Stefano Tessaro. Efficient and optimally secure key-length extension for block ciphers via randomized cascading. EUROCRYPT 2012.
- Martin Stanek. Threshold encryption into multiple ciphertexts. FPS 2012.
- Michal Rjaško. On Pseudo-Random Oracles. TatraCrypt 2012.
- Jaroslav Janáček, Martin Jurčík. Implementation of two-dimesional security model with partially trusted subjects using SELinux DTE and MLS. ITAT 2011.
- Daniel Olejár. Znalostné štandardy v informačnej bezpečnosti. Informačná bezpečnosť 2011.
- Richard Ostertág, Martin Stanek. Experience form searching for pseudorandom number generator. ITAT 2011.
- Michal Rjaško. Black-box property of cryptographic hash functions. FPS 2011.
Diskrétna matematika
V oblasti teórie grafov sa skupina špecializuje na farbenia, najmä hranové farbenia kubických grafov, toky na grafoch, vnáranie grafov do plôch a symetrie grafov. Druhá časť skupiny sa venuje štúdiu booleovských funkcií pomocou kombinatoricko-pravdepodobnostných metód a náhodných grafov a ich aplikácií (napr. komunikácia v sieťach).
Členovia skupiny:
Barbora Candráková, Lucia Haviarová, Michal Kotrbčík, Rastislav Královič, Tomáš Kulich, Edita Máčajová, Ivana Selečéniová, Martin Škoviera, Martin Stanek, Eduard Toman
Vybrané publikácie:
- Stefan Dobrev, Rastislav Královič, Dana Pardubská, and Imrich Vrťo. Antibandwidth and cyclic antibandwidth of Hamming graphs. Discrete Applied Mathematics 2013.
- Jakub Daubner, Eduard Toman. Neighbourhood of Constant Order in the Interval Graph of a Random Boolean Function. Fundamenta Informaticae 2013.
- Edita Máčajová. Bridgeless Cubic Graphs Are (7, 2)-Edge-Choosable. SIAM Journal on Discrete Mathematics 2013.
- Edita Máčajová, Ján Mazák. On even cycle decompositions of 4-regular line graphs. Discrete Mathematics 2013.
- Aleksander Malnič, Roman Nedela, Martin Škoviera. Regular maps with nilpotent automorphism groups. European Journal of Combinatorics 2012.
- Michal Kotrbčík, Martin Škoviera. Matchings, cycle bases, and the maximum genus of a graph. The Electronic Journal of Combinatorics 2012.
- Edita Rollová, Martin Škoviera. Nowhere-zero flows in Cartesian bundles of graphs. European Journal of Combinatorics 2012.
- Karina Chudá, Martin Škoviera. L (2, 1)-labelling of generalized prisms. Discrete Applied Mathematics 2012.
- Ján Karabáš, Edita Máčajová, Roman Nedela. 6-decomposition of snarks. European Journal of Combinatorics 2012.
- Lars Døvling Andersen, Edita Máčajová, Ján Mazák. Optimal acyclic edge‐coloring of cubic graphs. Journal of Graph Theory 2012.
- Michal Kotrbčík. A note on disjoint cycles. Information Processing Letters 2012
- Tomáš Kulich. The diameter of a random subgraph of the hypercube. Random Structures and Algorithms 2012.
- Robert Lukoťka, Edita Máčajová, Ján Mazák, Martin Škoviera. Circuits of length 5 in 2-factors of cubic graphs. Discrete Mathematics 2012.
- Mike J. Grannell, Terry S. Griggs, Edita Máčajová, Martin Škoviera. Coloring Cubic Graphs by Point‐Intransitive Steiner Triple Systems. Journal of Graph Theory 2012.
- Martin Nehéz, Daniel Olejár, Michal Demetrian. A detailed study of the dominating cliques phase transition in random graphs. TAMC 2012.
- Tomáš Kulich, Miroslava Kemeňová. On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász Local Lemma. Information Processing Letters 2011.
- Edita Máčajová, André Raspaud, Michael Tarsi, Xuding Zhu. Short cycle covers of graphs and nowhere‐zero flows. Journal of Graph Theory 68, no. 4 (2011): 340-348.
- Edita Máčajová, Martin Škoviera. Infinitely many Hypohamiltonian cubic graphs of girth 7. Graphs and Combinatorics 2011.
- Robert Lukoťka, Martin Škoviera. Snarks with given real flow numbers. Journal of Graph Theory 2011.
Distribuované a paralelné algoritmy
V poslednej dobe sa skupina zameriava na šírenie informácie v prostredí s chybnými linkami, najmä na deterministické modely chýb v sieťach. Cieľom je navrhovať protokoly, ktoré sú schopné korektne pracovať aj vo veľmi nespoľahlivých prostrediach, aké sa typicky vyskytujú pri senzorových a mobilných sieťach.
Členovia skupiny:
Rastislav Královič, Dana Pardubská, Tomáš Plachetka, Milan Plžík
Vybrané publikácie:
- Broňa Brejová, Stefan Dobrev, Rastislav Královič, Tomáš Vinař. Routing in carrier-based mobile networks. Theoretical Computer Science 2013.
- Stefan Dobrev, Paola Flocchini, Rastislav Královič, Nicola Santoro. Exploring an unknown dangerous graph using tokens. Theoretical Computer Science 2012.
- Stefan Dobrev, Rastislav Královič, Euripides Markou. Online graph exploration with advice. SIROCCO 2012.
- Stefan Dobrev, Evangelos Kranakis, Oscar Morales Ponce, and Milan Plžík. Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs. CSR 2012.
- Jurek Czyzowicz, Stefan Dobrev, Hernán González-Aguilar, Rastislav Královič, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho, Jorge Urrutia. Local 7-coloring for planar subgraphs of unit disk graphs. Theoretical Computer Science 412, no. 18 (2011).
Bioinformatika
Skupina sa zameriava najmä na výpočtovú analýzu funkcie a evolúcie genomickej DNA, ale aj ďašie problémy vo výpočtovej biológii. Skúmajú sa efektívne algoritmy, využitie pravdepodobnostných modelov, ako aj tvorba praktických sofvérových nástrojov a analýza konkrétnych biologických dát. Viac informácií na stránke skupiny.
Členovia skupiny:
Bronislava Brejová, Jaroslav Budiš, Jakub Kováč, Michal Nánási
Vybrané publikácie:
- Jakub Kováč. Complexity of the path avoiding forbidden pairs problem revisited. Discrete Applied Mathematics 2013.
- Katharina Jahn, Chunfang Zheng, Jakub Kováč, David Sankoff. A consolidation algorithm for genomes fractionated after higher order polyploidization. BMC Bioinformatics 2012.
- Jakub Kováč, Robert Warren, Marilia D. V. Braga, Jens Stoye. Restricted DCJ Model: Rearrangement Problems with Chromosome Reincorporation. Journal of Computational Biology 2011.
- Orangutan Genome Sequencing and Analysis Consortium (B. Brejová bola členkou konzorcia). Comparative and demographic analysis of orang-utan genomes. Nature 2011.
- Matúš Valach, Zoltan Farkas, Dominika Fričová, Jakub Kováč, Broňa Brejová, Tomáš Vinar, Ilona Pfeiffer, Judit Kucsera, Ľubomír Tomáška, B. Franz Lang, Jozef Nosek. Evolution of linear chromosomes and multipartite genomes in yeast mitochondria. Nucleic Acids Research 2011.
- Tomáš Kulich, Jaroslav Flegr. Positive effects of multiple gene control on the spread of altruism by group selection. Journal of Theoretical Biology 2011.
- Broňa Brejová, Gad M. Landau, Tomáš Vinař. Fast Computation of a String Duplication History under No-Breakpoint-Reuse. SPIRE 2011.
- Jakub Kováč, Broňa Brejová, Tomáš Vinař. A Practical Algorithm for Ancestral Rearrangement Reconstruction. WABI 2011.