Struktury a algoritmy ve velmi symetrických grafech

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

Standardní projekty 23 (SGA0201900001)

Hlavní účastníci

Univerzita Karlova / Matematicko-fyzikální fakulta

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

19-08554S

Název projektu anglicky

Structures and algorithms in highly symmetric graphs

Anotace anglicky

Highly symmetric graphs appear naturally in many different problems in computer science and discrete mathematics, for instance in coding theory, extremal combinatorics or in the study of Boolean functions. The algorithmic problem of generating all objects of a particular combinatorial class - such as bitstrings, permutations, partitions or trees - is another source of a multitude of highly symmetric graphs. In this project, we will investigate fundamental graph structures such as Hamilton cycles, matchings, and colorings in several families of highly symmetric graphs, with an emphasis on algorithmic applications. The core of the proposal are several far-ranging generalizations of the well-known middle levels conjecture, the Ruskey-Savage problem on matching extendability, and Gray code algorithms for different combinatorial objects.

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 čerpal finanční prostředky dle plánu. Splnil původně stanovené cíle a významně překročil počet plánovaných publikací. Ty byly často publikovány na významných fórech. Díky množství významných výsledků lze projekt považovat za splněný.

Zahájení řešení

1. 1. 2019

Ukončení řešení

30. 6. 2022

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

1. 4. 2022

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

CEP23-GA0-GA-U

Datum dodání záznamu

26. 6. 2023

Celkové uznané náklady

6 482 tis. Kč

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

6 215 tis. Kč

Ostatní veřejné zdroje financování

267 tis. Kč

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

0 tis. Kč