Go to main content | Go to main menu | Go to search

Project information
Structural properties, parameterized tractability and hardness in combinatorial problems

Information

This project doesn't include Faculty of Education. It includes Faculty of Informatics. Official project website can be found on muni.cz.
Investor logo
Project Identification
GA17-00837S
Project Period
1/2017 - 12/2019
Investor / Pogramme / Project type
Czech Science Foundation
  • Standard Projects
MU Faculty or unit
Faculty of Informatics

The concept of parameterized tractability allows for guaranteed efficient solutions of some instances - as determined by the parameter, of problems which are intractable in their full generality. Our proposal addresses various questions belonging to theoretical foundations of parameterized algorithmics, namely those related to structural and topological graph theory, and to logic and interpretations in graphs. Among the problems we propose to investigate are algorithmic metatheorems for FO properties on dense graph classes, FO interpretations in sparse classes and their structural characterizations, parameterized tractability of graph crossing number and planar insertion problems, structural characterization of crossing-critical graphs, and other.

Publications

Total number of publications: 15

2018

2017

Previous 1 2 Next

You are running an old browser version. We recommend updating your browser to its latest version.