Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 14 (SGA02011GA-ST)
Hlavní účastníci
—
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
P202-11-0196
Alternativní jazyk
Název projektu anglicky
Well-structured combinatorial classes, width parameters, and design of efficient algorithms
Anotace anglicky
Many important algorithmic problems are known to be NP-hard and thus it is unlikely that they could be solved efficiently on all possible inputs. One approach to cope with such problems is the use of parameterized complexity theory: the difficulty of inputs is classified by an additional parameter and algorithms are designed to efficiently solve problems on inputs with a bounded parameter. Our goal is to obtain new structural results on classes of (sparse) combinatorial objects, particularly on objectswith bounded width parameters, and apply these new results in the design of parameterized algorithms.
Vědní obory
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í dokončeného projektu
Hodnocení poskytovatelem
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
Byly dosaz?eny nove? teoreticke? vy?sledky na svetove urovni.
Termíny řešení
Zahájení řešení
1. 1. 2011
Ukončení řešení
31. 12. 2013
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
7. 6. 2013
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
CEP14-GA0-GA-U/01:1
Datum dodání záznamu
1. 7. 2014
Finance
Celkové uznané náklady
4 928 tis. Kč
Výše podpory ze státního rozpočtu
4 928 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč