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

Algorithms and Complexity within and beyond Bounded Expansion

Public support

  • Provider

    Ministry of Education, Youth and Sports

  • Programme

    ERC CZ

  • Call for proposals

    SMSM2020LL002

  • Main participants

    Univerzita Karlova / Matematicko-fyzikální fakulta

  • Contest type

    VS - Public tender

  • Contract ID

    MSMT-19250/2020

Alternative language

  • Project name in Czech

    Algoritmy a složitost v rámci a nad omezenou expanzí

  • Annotation in Czech

    Realizace projektu hraničního výzkumu v oblasti strukturální "teorie grafů, se zaměřením na aplikace v návrhu aproximačních a parametrizovaných algoritmů a na získání odpovídajících dolních mezí na složitost. Cílem je vybudovat detailní teorii omezené expanze v bodech, kde dochází ke kvalitativní změně chování (teorie expanze blízké konstantní, polynomiální, a exponenciální).

Scientific branches

  • R&D category

    ZV - Basic research

  • OECD FORD - main branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

  • OECD FORD - secondary branch

    10101 - Pure mathematics

  • OECD FORD - another secondary branch

  • CEP - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)

    AF - Documentation, librarianship, work with information<br>BA - General mathematics<br>BC - Theory and management systems<br>BD - Information theory<br>IN - Informatics

Completed project evaluation

  • Provider evaluation

    V - Vynikající výsledky projektu (s mezinárodním významem atd.)

  • Project results evaluation

    Graphs (networks) representing many practical problems (in geograpy, physics, biology, ...) exhibit sparsity properties that can be exploited in algorihmic design. The team explored the structure of paths and separators and applied it to obtain geometrie representations and approximation algorithms for such graph classes.

Solution timeline

  • Realization period - beginning

    Jun 1, 2020

  • Realization period - end

    May 31, 2022

  • Project status

    U - Finished project

  • Latest support payment

    May 4, 2022

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

    CEP23-MSM-LL-U

  • Data delivery date

    Jun 30, 2023

Finance

  • Total approved costs

    7,167 thou. CZK

  • Public financial support

    7,167 thou. CZK

  • Other public sources

    0 thou. CZK

  • Non public and foreign sources

    0 thou. CZK