Tight Parameterized Results for Directed Connectivity Problems
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 21 (SGA0201700001)
Main participants
České vysoké učení technické v Praze / Fakulta informačních technologií
Contest type
VS - Public tender
Contract ID
17-20065S
Alternative language
Project name in Czech
Těsné parametrizované výsledky pro problémy orientované souvislosti
Annotation in Czech
Parametrizovaná nebo multivarietní analýza se v minulých dvou dekádách stala standardním přístupem k (NP-) těžkým problémům. Oproti klasické výpočetní složitosti se zde efektivita algoritmů měří nejen vzhledem k délce vstupu, ale také vzhledem k určenému parametru. V poslední době je kladen větší důraz na získání nejlepšího možného stupně polynomu stejně jako nejlepší asymptotické časové závislosti na parametru. To je prokázáno předvedením dolních mezí ukazujících, že existence výrazně rychlejších algoritmů je nepravděpodobná, typicky založených na hypotéze exponenciálního času, nebo její silné formě. V tomto návrhu projektu se zaměřujeme na několik zásadních problémů v návrhu sítí spojených se souvislostí v orientovaných grafech z parametrizovaného pohledu. Náš cíl je buď získat nové algoritmy pro tyto problémy s lepší časovou složitostí než mají existující algoritmy, nebo získat dolní meze ukazující, že takové vylepšení je nepravděpodobné. Naším hlavním zaměřením jsou problémy Steinerovského typu na orientovaných grafech.
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
IN - Informatics
CEP - secondary branch
—
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project team achieved a number of results in the area of parameterized complexity. The course of the project was in line with its proposal, and likewise the quantity and the quality of the results obtained. The inclusion of PhD students to the work on the project and substantial international cooperation are commended. The funding was spent following the rules of the Czech Science Foundation.
Solution timeline
Realization period - beginning
Jan 1, 2017
Realization period - end
Dec 31, 2019
Project status
U - Finished project
Latest support payment
Apr 3, 2019
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP20-GA0-GA-U/02:1
Data delivery date
Jul 23, 2020
Finance
Total approved costs
1,986 thou. CZK
Public financial support
1,620 thou. CZK
Other public sources
366 thou. CZK
Non public and foreign sources
0 thou. CZK