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