Nakrývání grafů: Symetrie a složitost

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

SGA0202000001

Hlavní účastníci

Univerzita Karlova / Matematicko-fyzikální fakulta

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

20-15576S

Název projektu anglicky

Graph Covers: Symmetries and Complexity

Anotace anglicky

The concept of symmetry is as old as mathematics. In modern mathematics, it is formalized by the concept of the automorphism of a considered structure. In the present project we shall restrict ourselves to investigation of one- and two-dimensional structures, namely, to graphs, surfaces, and their quotients, that is to orbifolds of dimension 1 and 2. Coverings between graphs and surfaces were extensively investigated and found many applications. Much less is known about the computational complexity of graph covering problems. The project is aimed at investigation of computational complexity of such problems, including several problems that either generalize the graph isomorphism problem, or ask to solve it for restricted classes of graphs. In this framework we hope to understand better the behavior of the complexity of the problems under investigation with the aim to identify the borderline between P and GI-completeness on one-hand side, and GI-completeness and NP-hardness on the other one.

Kategorie VaV

ZV - Základní výzkum

OECD FORD - hlavní obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

OECD FORD - vedlejší obor

—

OECD FORD - další vedlejší obor

—

CEP - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

AF - Dokumentace, knihovnictví, práce s informacemi<br>BC - Teorie a systémy řízení<br>BD - Teorie informace<br>IN - Informatika

Hodnocení poskytovatelem

U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)

Zhodnocení výsledků projektu

Projekt vedl k velkému množství dobrých publikací v respektovaných mezinárodních konferencích a časopisech, což je uspokojivé vzhledem k velikosti a potenciálu týmu. Slabinou je velmi nízký počet excelentních publikací (žádná konference CORE A*, 1 článek v JCTB).

Zahájení řešení

1. 1. 2020

Ukončení řešení

30. 6. 2023

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

1. 4. 2023

Důvěrnost údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Systémové označení dodávky dat

CEP24-GA0-GA-U

Datum dodání záznamu

21. 5. 2024

Celkové uznané náklady

8 573 tis. Kč

Výše podpory ze státního rozpočtu

7 581 tis. Kč

Ostatní veřejné zdroje financování

992 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč