Structures and algorithms in highly symmetric graphs
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 23 (SGA0201900001)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
19-08554S
Alternative language
Project name in Czech
Struktury a algoritmy ve velmi symetrických grafech
Annotation in Czech
Velmi symetrické grafy se přirozeně vyskytují v mnoha různých problémech informatiky a diskrétní matematiky, například v teorii kódování, extremální kombinatorice nebo ve studiu Booleovských funkcí. Dalším zdrojem plejády velmi symetrických grafů jsou algoritmické problémy generování všech objektů z daných kombinatorických tříd jakou jsou bitové řetězce, permutace, rozklady či stromy. V tomto projektu budeme zkoumat fundamentální grafové struktury jako jsou Hamiltonovské cykly, párování a barvení v různých třídách velmi symetrických grafů s důrazem na algoritmické aplikace. Jádrem návrhu je několik širokých zobecnění velmi známé hypotézy prostředních vrstev, problém Ruskeyho a Savageové o rozšiřitelnosti párováních a algoritmy pro Grayovy kódy různých kombinatorických objektů.
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
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The financial aspects of the project are in line with the plan. The project fulfilled the original aims and significantly exceeded the number of planned publications. These were often published at essential venues. Therefore, the project reached very good results and should be evaluated accordingly.
Solution timeline
Realization period - beginning
Jan 1, 2019
Realization period - end
Jun 30, 2022
Project status
U - Finished project
Latest support payment
Apr 1, 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
6,482 thou. CZK
Public financial support
6,215 thou. CZK
Other public sources
267 thou. CZK
Non public and foreign sources
0 thou. CZK