All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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