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

Project information
Structure of tractable instances of hard algorithmic problems on graphs

Investor logo
Project Identification
GA20-04567S
Project Period
1/2020 - 12/2022
Investor / Pogramme / Project type
Czech Science Foundation
  • Standard Projects
MU Faculty or unit
Faculty of Informatics

One of the fundamental questions in theoretical CS is how to approach problems which are intractable in their full generality. Our proposal is to investigate the internal structure of tractable instances of such generally hard problems on graphs, namely those dealing with structural and topological graph theory, geometric graphs, and of problems definable in various logics. In particular, we propose to investigate algorithmic and complexity theoretical aspects of new width and sparsity parameters of graph classes, properties of geometric representations of graphs, tractable instances for the FO model checking problem, and the detailed structure of the graph crossing number problem.

Sustainable Development Goals

Masaryk University is committed to the UN Sustainable Development Goals, which aim to improve the conditions and quality of life on our planet by 2030.

Sustainable Development Goal No. 9 – Industry, innovation and infrastructure

Publications

Total number of publications: 21

2022

2021

2020

  • Clique-Width of Point Configurations

    CAGIRICI Onur HLINĚNÝ Petr POKRÝVKA Filip SANKARAN Abhisekh

    Article in Proceedings

    Graph-Theoretic Concepts in Computer Science, WG 2020, year: 2020

  • Isomorphism Problem for Sd-Graphs

    AGAOGLU Deniz HLINĚNÝ Petr

    Article in Proceedings

    45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), year: 2020

Previous 1 2 3 Next

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

More info