Struktury a algoritmy ve velmi symetrických grafech
Cíle projektu
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ů.
Klíčová slova
hypercubeKneser graphHamilton cyclematchingGray codemiddle levels conjectureposetdiscrete geometry
Veřejná podpora
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
Alternativní jazyk
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.
Vědní obory
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
(dle převodníku)AF - Dokumentace, knihovnictví, práce s informacemi
BC - Teorie a systémy řízení
BD - Teorie informace
IN - Informatika
Hodnocení dokončeného projektu
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ý.
Termíny řešení
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
Dodání dat do CEP
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
Finance
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č
Základní informace
Uznané náklady
6 482 tis. Kč
Statní podpora
6 215 tis. Kč
95%
Poskytovatel
Grantová agentura České republiky
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Doba řešení
01. 01. 2019 - 30. 06. 2022