Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

SGA0202000001

Hlavní účastníci

Masarykova univerzita / Fakulta informatiky

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

20-04567S

Název projektu anglicky

Structure of tractable instances of hard algorithmic problems on graphs

Anotace anglicky

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.

Kategorie VaV

ZV - Základní výzkum

OECD FORD - hlavní obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

OECD FORD - vedlejší obor

—

OECD FORD - další vedlejší obor

—

CEP - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

AF - Dokumentace, knihovnictví, práce s informacemi<br>BC - Teorie a systémy řízení<br>BD - Teorie informace<br>IN - Informatika

Hodnocení poskytovatelem

V - Vynikající výsledky projektu (s mezinárodním významem atd.)

Zhodnocení výsledků projektu

Projekt vedl k několika velmi dobrým a mnoha dobrým publikacím, takže jeho výsledky jsou velmi dobré. Projekt úspěšně zapojil řadu mladých výzkumníků.

Zahájení řešení

1. 1. 2020

Ukončení řešení

31. 12. 2022

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

11. 5. 2022

Důvěrnost údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Systémové označení dodávky dat

CEP23-GA0-GA-U

Datum dodání záznamu

26. 6. 2023

Celkové uznané náklady

8 174 tis. Kč

Výše podpory ze státního rozpočtu

6 521 tis. Kč

Ostatní veřejné zdroje financování

1 653 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč