Contact

Robert Ganian
Institute of Information Systems (184/3)
Vienna University of Technology (TU Wien)
Favoritenstrasse 9-11
A-1040 Vienna, Austria

Phone: +43 (1) 58801 184833
Mobile: +420 608 566012
e-mail: rganian ( at ) gmail ( dot ) com

Research

My area of research is Theoretical Computer Science, specifically:
  • Parameterized complexity and kernelization
  • Algorithmic meta-theorems
  • Algorithmic graph Theory

This research is carried out as part of the project "The Parameterized Complexity of Reasoning Problems" under the supervision of Stefan Szeider.

Conference publications

  1. Meta-Kernelization with Structural Parameters.
    Proceedings of MFCS 2013. To appear.
    (with Friedrich Slivovsky and Stefan Szeider)
  2. FO Model Checking of Interval Graphs.
    Proceedings of ICALP 2013. To appear.
    (with Petr Hliněný, Daniel Král, Jan Obdržálek, Jarett Schwartz and Jakub Teska)
  3. Expanding the expressive power of Monadic Second-Order logic on restricted graph classes.
    Proceedings of IWOCA 2013. To appear.
    (with Jan Obdržálek)
  4. When Trees Grow Low: Shrubs and Fast MSO1.
    Proceedings of MFCS 2012. Lecture Notes in Computer Science, vol. 7464, pp. 419-430, 2012.
    (with Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek, Patrice Ossona de Mendez and Reshma Ramadurai)
  5. Using Neighborhood Diversity to Solve Hard Problems.
    Proceedings of SOFSEM 2012. Local proceedings, 11 p., 2012.
  6. Lower Bounds on the Complexity of MSO1 Model-Checking.
    Proceedings of STACS 2012. LIPIcs, vol. 14, pp. 326-337, 2012.
    (with Petr Hliněný, Alexander Langer, Jan Obdrzálek, Peter Rossmanith and Somnath Sikdar)
  7. Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics.
    Proceedings of IPEC 2011. Lecture Notes in Computer Science, vol. 7112, pp. 259-271, 2011.
  8. New Results on the Complexity of the Max- and Min-Rep Problems.
    Proceedings of SOFSEM 2011. Lecture Notes in Computer Science, vol. 6543, pp. 238-247, 2011.
    (Best Student Paper Award)
  9. Clique-width: When Hard Does Not Mean Impossible.
    Proceedings of STACS 2011. LIPIcs, vol. 9, pp. 404-415, 2011.
    (with Petr Hliněný and Jan Obdrzálek)
  10. Thread graphs, linear rank-width and their algorithmic applications.
    Proceedings of IWOCA 2010. Lecture Notes in Computer Science, vol. 6460, pp. 38-42, 2010.
  11. New results on the complexity of oriented colouring on restricted digraph classes.
    Proceedings of SOFSEM 2010. Lecture Notes in Computer Science, vol. 5901, pp. 428-439, 2010.
    (with Petr Hliněný)
  12. Are there any good digraph width measures?
    Proceedings of IPEC 2010. Lecture Notes in Computer Science, vol. 6478, pp. 135-146, 2010.
    (with Petr Hliněný, Joachim Kneis, Jan Obdrzálek, Peter Rossmanith and Somnath Sikdar)
  13. Better algorithms for satisfiability problems for formulas of bounded rank-width.
    Proceedings of FSTTCS 2010. LIPIcs, vol. 8, pp. 73-83, 2010.
    (with Petr Hliněný and Jan Obdrzálek)
  14. The Parameterized Complexity of Oriented Colouring.
    Proceedings of MEMICS 2009. DROPS, vol. 13, 12 p., 2009.
  15. Better Polynomial Algorithms on Graphs of Bounded Rank-Width.
    Proceedings of IWOCA 2009. Lecture Notes in Computer Science, vol. 5874, pp. 266-277, 2009.
    (with Petr Hliněný)
  16. On Digraph Width Measures in Parameterized Algorithmics.
    Proceedings of IWPEC 2009. Lecture Notes in Computer Science, vol. 5917, pp. 185-197, 2009.
    (with Petr Hliněný, Joachim Kneis, Alexander Langer, Jan Obdrzálek and Peter Rossmanith)
  17. Automata approach to graphs of bounded rank-width.
    Proceedings of IWOCA 2008. College Publications, pp. 4-15.
    (with Petr Hliněný)

Journal publications

  1. Lower Bounds on the Complexity of MSO1 Model-Checking.
    Journal of Computer and System Sciences, to appear.
    (with Petr Hliněný, Alexander Langer, Jan Obdrzálek, Peter Rossmanith and Somnath Sikdar)
  2. Cops-and-robbers: remarks and problems.
    Journal of Combinatorial Mathematics and Combinatorial Computing, to appear.
    (with Michel Boyer, Sif El Harti, Amal El Ouarari, Geňa Hahn, Carsten Moldenauer, Ignaz Rutter, Benoit Thériault and Martin Vatshelle)
  3. A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width.
    European Journal of Combinatorics 34 (3), pp. 680-701, 2013.
    (with Petr Hliněný and Jan Obdrzálek)
  4. Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width.
    Fundamenta Informaticae 123 (1), pp. 59-76, 2013.
    (with Petr Hliněný and Jan Obdrzálek)
  5. On Parse Trees and Myhill-Nerode-type Tools for handling Graphs of Bounded Rank-width.
    Discrete Applied Mathematics 158 (7), pp. 851-867, 2010.
    (with Petr Hliněný)