Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

Standardní projekty 21 (SGA0201700001)

Hlavní účastníci

Masarykova univerzita / Fakulta informatiky

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

17-00837S

Název projektu anglicky

Structural properties, parameterized tractability and hardness in combinatorial problems

Anotace anglicky

The concept of parameterized tractability allows for guaranteed efficient solutions of some instances - as determined by the parameter, of problems which are intractable in their full generality. Our proposal addresses various questions belonging to theoretical foundations of parameterized algorithmics, namely those related to structural and topological graph theory, and to logic and interpretations in graphs. Among the problems we propose to investigate are algorithmic metatheorems for FO properties on dense graph classes, FO interpretations in sparse classes and their structural characterizations, parameterized tractability of graph crossing number and planar insertion problems, structural characterization of crossing-critical graphs, and other.

Kategorie VaV

ZV - Základní výzkum

CEP - hlavní obor

IN - Informatika

CEP - vedlejší obor

BA - Obecná matematika

CEP - další vedlejší obor

—

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

10101 - Pure mathematics<br>10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Hodnocení poskytovatelem

U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)

Zhodnocení výsledků projektu

Projekt přinesl nové vědecké výsledky v parametrizované teorii složitosti, strukturální teorii grafů, vlastnostech topologických a geometrických grafů, zejména průsečníkových čísel. Výsledky jsou publikovány v předních časopisech v oboru a na kvalitních konferencích. Závěrečná karta dostatečně charakterizuje výsledky projektu. Grantová pravidla byla dodržena.

Zahájení řešení

1. 1. 2017

Ukončení řešení

31. 12. 2019

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

3. 4. 2019

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

CEP20-GA0-GA-U/02:1

Datum dodání záznamu

23. 7. 2020

Celkové uznané náklady

4 758 tis. Kč

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

3 294 tis. Kč

Ostatní veřejné zdroje financování

1 440 tis. Kč

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

0 tis. Kč