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”

Structural properties, parameterized tractability and hardness in combinatorial problems

Public support

  • Provider

    Czech Science Foundation

  • Programme

    Standard projects

  • Call for proposals

    Standardní projekty 21 (SGA0201700001)

  • Main participants

    Masarykova univerzita / Fakulta informatiky

  • Contest type

    VS - Public tender

  • Contract ID

    17-00837S

Alternative language

  • Project name in Czech

    Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech

  • Annotation in Czech

    Pojetí parametrizované složitosti poskytuje garantovaná efektivní řešení některých instancí (definovaných daným parametrem) u problémů, které jsou v celé své obecnosti efektivně neřešitelné. Náš návrh se týká různých otázek náležejících do teoretických základů parametrizované algoritmiky, především těch vztahujících se ke strukturální a topologické teorie grafů, logice a interpretacím grafů. Mezi problémy, které budeme zkoumat, náleží algoritmické metavěty pro FO vlastnosti na hustých třídách grafů, FO interpretace v řídkých třídách a jejich strukturální charakterizace, parametrizovaná řešitelnost problémů průsečíkového čísla grafu a rovinného vkládání, strukturální popis průsečíkově-kritických grafů a další.

Scientific branches

  • R&D category

    ZV - Basic research

  • CEP classification - main branch

    IN - Informatics

  • CEP - secondary branch

    BA - General mathematics

  • 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>)

    10101 - Pure mathematics<br>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

    Project resulted into new research results in parametrized complexity theory, structural graph theory, properties of topological and geometric graphs, namely crossing numbers. Results are published in leading journals and rank A or B conferences. The final card sufficiently characterizes the project results. Agency rules were obeyed.

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

    4,758 thou. CZK

  • Public financial support

    3,294 thou. CZK

  • Other public sources

    1,440 thou. CZK

  • Non public and foreign sources

    0 thou. CZK