Přejít k obsahu | Přejít k hlavnímu menu | Přejít k vyhledávání

Informace o projektu
Structure of tractable instances of hard algorithmic problems on graphs

Logo poskytovatele
Kód projektu
GA20-04567S
Období řešení
1/2020 - 12/2022
Investor / Programový rámec / typ projektu
Grantová agentura ČR
  • Standardní projekty
Fakulta / Pracoviště MU
Fakulta informatiky

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.

Cíle udržitelného rozvoje

Masarykova univerzita se hlásí k cílům udržitelného rozvoje OSN, jejichž záměrem je do roku 2030 zlepšit podmínky a kvalitu života na naší planetě.

Cíl udržitelného rozvoje č. 9 – Průmysl, inovace a infrastruktura

Publikace

Počet publikací: 17

2023

2022

2021

Předchozí 1 2 Další

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info