Těsné parametrizované výsledky pro problémy orientované souvislosti

Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 21 (SGA0201700001)
Hlavní účastníci
České vysoké učení technické v Praze / Fakulta informačních technologií
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
17-20065S

Název projektu anglicky
Tight Parameterized Results for Directed Connectivity Problems
Anotace anglicky
A parameterized or multivariate analysis became in the last two decades a standard approach for (NP-) hard computational problems. Here, in contrast to classical complexity, the efficiency of algorithms is not measured only with respect to the length of the input instance, but also with respect to a specified parameter. Recently, more focus is put on achieving the best possible polynomial degree as well as the best asymptotic time dependency on the parameter. This is justified by providing matching lower bounds, showing that the existence of significantly faster algorithms is improbable, typically relying on the Exponential Time Hypothesis or its strong form. In this research proposal we target on several fundamental problems in network design related to connectivity in directed graphs from the parameterized perspective. Our aim is to either obtain new algorithms for the problems with better running time than that of the existing algorithms, or to obtain lower bounds showing that such an improvement is unlikely. Our main focus are Steiner-type problems in directed graphs.

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í poskytovatelem
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Řešitelský tým dosáhl řadu výsledků v oblasti parametrizované složitosti. Postup řešení probíhal v souladu s návrhem projektu; množství a kvalita výsledků odpovídá údajům uvedeným v návrhu projektu. Pozitivně lze hodnotit zapojení doktorandů a významné spolupráci se zahraničními pracovišti. Finance byly čerpány v souladu s pravidly GA ČR.

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

Podobné projekty(10)