Parameterized Algorithms for Fundamental Network Problems Related to Connectivity
Public support
Provider
Czech Science Foundation
Programme
Post-graduate (doctorate) grants
Call for proposals
Postdoktorandské granty 15 (SGA0201400003)
Main participants
České vysoké učení technické v Praze / Fakulta informačních technologií
Contest type
VS - Public tender
Contract ID
14-13017P
Alternative language
Project name in Czech
Parametrizované algoritmy pro základní síťové problémy spojené se souvislostí
Annotation in Czech
Parametrizované algoritmy se staly v posledních dvou dekádách standardním nástrojem pro řešení výpočetně těžkých (NP-těžkých) problémů. Časová složitost se v tomto vyjadřuje pomocí druhotné míry (parametru) navíc k velikosti vstupu, čímž se dosahuje jemnější analýza původu těžkosti problému. Parametrizovaná složitost představuje matematický rámec pro analyzování takových algoritmů a také umožnuje ukázat, že pro některé problémy a parametry (pravděpodobně) žádný takový algoritmus neexistuje. V rámci toho projektu plánujeme studovat některé otevřené otázky související se základními problémy v oblasti návrhu sítí z pohledu parametrizované složitosti. Přesněji se zaměříme na tyto dvě oblasti: problémy Steinerovského typu v grafech a měření, navigace a umístění zdrojů v sítích. Plánujeme připravit systematickou multivarietní analýzu, která podle našeho názoru v této oblasti chybí.
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 contributed to understanding of algorithms and complexity on network connectivity, multi-cuts, Steiner type problems. The results are very good, and are adequate.
Solution timeline
Realization period - beginning
Jan 1, 2014
Realization period - end
Dec 31, 2016
Project status
U - Finished project
Latest support payment
Apr 5, 2016
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
CEP17-GA0-GP-U/01:1
Data delivery date
Jun 30, 2017
Finance
Total approved costs
1,649 thou. CZK
Public financial support
1,649 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK