Graph Covers: Symmetries and Complexity
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202000001
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
20-15576S
Alternative language
Project name in Czech
Nakrývání grafů: Symetrie a složitost
Annotation in Czech
Koncept symetrie je stejně starý jako matematika sama. V moderní matematice je formalizován jako koncept automorfismu uvažované struktury. V předkládaném projektu budeme studovat jedno- a dvou-dimenzionální struktury, zejména grafy, plochy a jejich kvocienty, tedy orbity dimenze 1 a 2. Nakrytí grafů a ploch byla intenzivně studována a našla mnoho aplikací. Mnohem méně je ale známo o výpočetní složitosti otázek souvisejících s nakrýváním grafů. Projekt se zaměří na studium výpočetní složitosti těchto otázek, včetně problémů zobecňujících problém isomorfismu grafů, případně tento problém řešící pro omezené třídy grafů. Tímto způsobem doufáme dosáhnout lepšího pochopení výpočetní složitosti studovaných problémů s nadějí na upřesnění hranice mezi polynomiálními a GI-úplnými instancemi na jedné straně, a mezi GI-úplnými a NP-úplnými instancemi na straně druhé.
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 project delivered a large number of good publications, published in respected international conferences and journals. The outcome is satisfactory for the size and potential of the team. On the negative side, the project resulted in very few top-shelf publication (no CORE A* conference paper, one JCTB paper).
Solution timeline
Realization period - beginning
Jan 1, 2020
Realization period - end
Jun 30, 2023
Project status
U - Finished project
Latest support payment
Apr 1, 2023
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
CEP24-GA0-GA-U
Data delivery date
May 21, 2024
Finance
Total approved costs
8,573 thou. CZK
Public financial support
7,581 thou. CZK
Other public sources
992 thou. CZK
Non public and foreign sources
0 thou. CZK