All
All

What are you looking for?

All
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”

Parameterized Algorithms for Fundamental Network Problems Related to Connectivity

Project goals

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.

Keywords

computational intractabilityproblem kernelpolynomial-time preprocessinggraph algorithmnetwork designW[1]-hardnessW[2]-hardnessfixed-parameter tractabilityconnectivitySteiner-type problems

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

  • 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

Basic information

Recognised costs

1 649 CZK thou.

Public support

1 649 CZK thou.

100%


Provider

Czech Science Foundation

CEP

IN - Informatics

Solution period

01. 01. 2014 - 31. 12. 2016