Graph Minors, Bidimensionality and Algorithms

Lecturer: Prof. Fedor Fomin (University of Bergen, Norway).

About the lecturer | Course Summary | Slides | Assignment

About the lecturer: Fedor Fomin received his Master (1992) and PhD (1997) degrees from the Faculty of Mathematics and Mechanics, St. Petersburg State University, supervised by Prof. Nikolay Petrov. He was an assistant professor at St. Petersburg State University (chair of Operations Research) till 1999. Then he was a postdoc in Chile (CMM and Universidad de Chile), in Czech Republic (ITI and Charles University), and in Germany (University of Paderborn). Since 2002, he is a professor in Algorithms, at the Department of Informatics, University of Bergen.

Fedor Fomin's interests include Parameterized Complexity, Algorithms, and Kernelization, Exact (exponential time) Algorithms, Graph Algorithmhs (in particular, Algorithmic Graph Minors, Graph Coloring, Graph widths parameters -- treewidth, branchwidth, clique-width, etc., Pursuit-evasion and Search problems.

In recognition of his work, he was invited to serve as an editor of SIAM J. Discrete Mathematics and as a program committee member of most influential conferences like ICALP, SODA, ESA, WG (chair in 2006), IWPEC (chair in 2009) and many others. He advised 3 PhD students.

Course summary: See Bidimensionality in Wikipedia.


Assignment: Tasks are here: [PDF]. Due: 10th February. Please send a pdf to prof. Fomin.