Algoritmy a složitost v rámci a nad omezenou expanzí
Veřejná podpora
Poskytovatel
Ministerstvo školství, mládeže a tělovýchovy
Program
ERC CZ
Veřejná soutěž
SMSM2020LL002
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
MSMT-19250/2020
Alternativní jazyk
Název projektu anglicky
Algorithms and Complexity within and beyond Bounded Expansion
Anotace anglicky
The project is in the area of the structural graph theory, with focus on the applications in the design of approximation and parameterized algorithms and on obtaining the corresponding complexity lower bounds. The goal is to develop the detailed theory of bounded expansion at the phase transition points where the behavior of the graph classes qualitatively changes (the theory of near constant, polynomial, and exponential expansion).
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
10101 - Pure mathematics
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>BA - Obecná matematika<br>BC - Teorie a systémy řízení<br>BD - Teorie informace<br>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
Grafy (sítě) reprezentující praktické problémy (v geografii, fyzice, biologii, ...) typicky mají speciální vlastnosti, které omezují jejich složitost a které mohou být 6 Zaz 202 využity algoritmicky. Řešitelský tým studoval strukturu cest a vyvážených řezů v takových grafech a získané výsledky využil k nalezení jejich geometrických reprezentací a v návrhu aproximačních algoritmů.
Termíny řešení
Zahájení řešení
1. 6. 2020
Ukončení řešení
31. 5. 2022
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
4. 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-MSM-LL-U
Datum dodání záznamu
30. 6. 2023
Finance
Celkové uznané náklady
7 167 tis. Kč
Výše podpory ze státního rozpočtu
7 167 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč