Structure of tractable instances of hard algorithmic problems on graphs
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202000001
Main participants
Masarykova univerzita / Fakulta informatiky
Contest type
VS - Public tender
Contract ID
20-04567S
Alternative language
Project name in Czech
Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech
Annotation in Czech
Jednou ze základních otázek teoretické informatiky je jak řešit algoritmické problémy, které jsou v plné obecnosti efektivně neřešitelné. Naším návrhem je zkoumat vnitřní strukturu efektivně řešitelných případů takových obecně těžkých problémů na grafech, především otázky z oblastí strukturální a topologické teorie grafů, geometrických grafů a ty týkající se problémů definovaných v různých logikách. Konkrétně navrhujeme studovat algoritmické a složitostní stránky nových šířkových a "řídkostních" parametrů tříd grafů, vlastnosti geometrických reprezentací grafů, efektivně řešitelné případy rozhodování FO vlastností a podrobnou strukturu problému průsečíkového čísla grafu.
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
—
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>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
The project resulted in a number of very good and a large volume of good publications, thus the outcome is very good. The project successfully involved a number of junior researchers.
Solution timeline
Realization period - beginning
Jan 1, 2020
Realization period - end
Dec 31, 2022
Project status
U - Finished project
Latest support payment
May 11, 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-GA0-GA-U
Data delivery date
Jun 26, 2023
Finance
Total approved costs
8,174 thou. CZK
Public financial support
6,521 thou. CZK
Other public sources
1,653 thou. CZK
Non public and foreign sources
0 thou. CZK