Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech
Cíle projektu
Jednou ze základních otázek teoretické informatiky je jak řešit algoritmické problémy, které jsou v plné obecnosti efektivně neřešitelné. Naším návrhem je zkoumat vnitřní strukturu efektivně řešitelných případů takových obecně těžkých problémů na grafech, především otázky z oblastí strukturální a topologické teorie grafů, geometrických grafů a ty týkající se problémů definovaných v různých logikách. Konkrétně navrhujeme studovat algoritmické a složitostní stránky nových šířkových a "řídkostních" parametrů tříd grafů, vlastnosti geometrických reprezentací grafů, efektivně řešitelné případy rozhodování FO vlastností a podrobnou strukturu problému průsečíkového čísla grafu.
Klíčová slova
graph theoryalgorithmic complexitywidth parametersmodel checkinggeometric graphcrossing number
Veřejná podpora
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
Alternativní jazyk
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.
Vědní obory
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
(dle převodníku)AF - Dokumentace, knihovnictví, práce s informacemi
BC - Teorie a systémy řízení
BD - Teorie informace
IN - Informatika
Hodnocení dokončeného projektu
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ů.
Termíny řešení
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
Dodání dat do CEP
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
Finance
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č
Základní informace
Uznané náklady
8 174 tis. Kč
Statní podpora
6 521 tis. Kč
79%
Poskytovatel
Grantová agentura České republiky
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Doba řešení
01. 01. 2020 - 31. 12. 2022