Parametrizované algoritmy pro základní síťové problémy spojené se souvislostí
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Postdoktorandské granty
Veřejná soutěž
Postdoktorandské granty 15 (SGA0201400003)
Hlavní účastníci
České vysoké učení technické v Praze / Fakulta informačních technologií
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
14-13017P
Alternativní jazyk
Název projektu anglicky
Parameterized Algorithms for Fundamental Network Problems Related to Connectivity
Anotace anglicky
Parameterized algorithmics became in the last two decades a standard tool to solve computationally hard (NP-hard) problems. The running time here is expressed in terms of a secondary measure (the parameter) additionally to the input size, which provides a more refined analysis of where the hardness of the problem comes from. Parameterized complexity provides a mathematical framework to analyze these algorithms and also to show that for some problems and parameters there is (probably) no such algorithm. In this research proposal we plan to study several open questions related to fundamental problems in the field of network design within the framework of parameterized complexity. More precisely, we will focus on the following two areas: Steiner-type problems in graphs; Network Measurement, Navigation, and Resource Placement. We plan to provide a systematic multivariate complexity analysis, which we feel is missing in the area.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
IN - Informatika
CEP - vedlejší obor
—
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>)
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
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Projekt přinesl nové poznatky o souvislosti sítí, o řezech a o problémech Steinerova typu. Výsledky jsou velmi dobré a jsou adekvátní. Grantová pravidla byla dodržena.
Termíny řešení
Zahájení řešení
1. 1. 2014
Ukončení řešení
31. 12. 2016
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
5. 4. 2016
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
CEP17-GA0-GP-U/01:1
Datum dodání záznamu
30. 6. 2017
Finance
Celkové uznané náklady
1 649 tis. Kč
Výše podpory ze státního rozpočtu
1 649 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč