Jan Obdrzalek

Associate Professor,
Department of Computer Science
Faculty of Informatics
Masaryk University

Contact information

Jan Obdržálek
Fakulta informatiky MU
Botanická 68a
602 00 Brno
Czech Republic
Office: C436
Phone: +420-549 494 225
Fax: +420-549 497 434
E-mail: obdrzalek (at) fi (dot) muni (dot) cz
public GPG/PGP key

Academic profile

Research interests

... in the past

Infinite games on graphs (esp. parity games), mu-calculus, automatic bug-finding, software verification, parallel programming.


Recent Papers

Kernelization using structural parameters on sparse graph classes (J. Gajarský, P. Hliněný, J. Obdržálek, S. Ordyniak, F. Reidl, P. Rossmanith, F. Sanchez Villaamil, S. Sikdar), In J. Comput. Syst. Sci., volume 84, 2017. [bibtex] [doi]
A New Perspective on FO Model Checking of Dense Graph Classes (J. Gajarský, P. Hliněný, J. Obdržálek, D. Lokshtanov, M. S. Ramanujan), In LICS'16, ACM, 2016. [bibtex] [doi]
Tree-depth and vertex-minors (P. Hliněný, O. Kwon, J. Obdržálek, S. Ordyniak), In Eur. J. Comb., volume 56, 2016. [bibtex] [doi]
Are there any good digraph width measures? (R. Ganian, P. Hliněný, J. Kneis, D. Meister, J. Obdržálek, P. Rossmanith, S. Sikdar), In J. Comb. Theory, Ser. B, volume 116, 2016. [bibtex] [doi]
FO Model Checking of Interval Graphs (R. Ganian, P. Hliněný, D. Krá\vl, J. Obdržálek, J. Schwartz, J. Teska), In Log. Methods Comput. Sci., volume 11, 2015. [bibtex] [doi]
FO Model Checking on Posets of Bounded Width (J. Gajarský, P. Hliněný, D. Lokshtanov, J. Obdržálek, S. Ordyniak, M. S. Ramanujan, S. Saurabh), In FOCS'15, IEEE Computer Society, 2015. [bibtex] [doi]
Faster Existential FO Model Checking on Posets (J. Gajarský, P. Hliněný, J. Obdržálek, S. Ordyniak), In Log. Methods Comput. Sci., volume 11, 2015. [bibtex] [doi]

Selected Additional Publications

DAG-width -- Connectivity Measure for Directed Graphs (J. Obdržálek), In SODA'06, ACM-SIAM, 2006. [bibtex] [doi]
Fast Mu-calculus Model Checking when Tree-width is Bounded (J. Obdržálek), In CAV 2003, Springer, volume 2725 of LNCS, 2003. [bibtex] [doi]


Algorithmic Analysis of Parity Games (J. Obdržálek), PhD thesis, University of Edinburgh, 2006. (Submitted: January 31, 2006. Examined: May 29, 2006) [bibtex] [full version]
Formal verification of sequential systems with infinitely many states (J. Obdržálek), Master's thesis, Masaryk University, Brno, 2001. [bibtex] [full version]


Fall 2017
Spring 2017
Selected courses in the past


In addition to the concrete thesis topics in the IS, I am happy to supervise other theses (both practical and theoretical), particularly (but not only) in the areas below. Do not hesitate to contact me if you are interested!

Selected former students (and their last known position)

Various resources

Jan Obdržálek

Last modified: February 13 2018 17:15:33.