Vše
Vše

Co hledáte?

Vše
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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