Principles of combinatorial generation
Project goals
Generation of combinatorial objects is a fundamental algorithmic task with a wide range of practical applications. This task leads to the definition of flip graphs, which have as vertices the objects to be generated, and edges connect objects that differ in a small change. The aim of this project is to (1) develop and extend the theoretical foundations for combinatorial generation, with a focus on algorithms and combinatorics, (2) investigate structural properties of the underlying flip graphs, which leads to several long-standing open problems, (3) implement new generation algorithms and make them available on the Combinatorial Object Server.
Keywords
combinatorial generationhighly symmetric graphsHamilton cyclehypercubegeometric flip graphs
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202200004
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
22-15272S
Alternative language
Project name in Czech
Principy kombinatorického generování
Annotation in Czech
Generování kombinatorických objektů je základní algoritmickou úlohou s širokou řadou praktických aplikací. Tato úloha vede k definici tzv. flip grafů, jež mají za vrcholy generované objekty a hrany spojují objekty, jež se od sebe málo odlišují. Cílem tohoto projektu je (1) rozvinout a rozšířit teoretické základy pro kombinatorické generování se zaměřením na algoritmy a kombinatoriku, (2) zkoumat strukturální vlastnosti příslušných flip grafů, které vedou k několika dlouhodobě otevřeným problémům, (3) naimplementovat nové algoritmy pro generování a zpřístupnit je na serveru kombinatorických objektů (Combinatorial Object Server).
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10102 - Applied mathematics
OECD FORD - secondary branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Solution timeline
Realization period - beginning
Jan 1, 2022
Realization period - end
Dec 31, 2024
Project status
—
Latest support payment
Feb 29, 2024
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
CEP25-GA0-GA-R
Data delivery date
Mar 12, 2025
Finance
Total approved costs
6,795 thou. CZK
Public financial support
6,552 thou. CZK
Other public sources
243 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
6 795 CZK thou.
Public support
6 552 CZK thou.
96%
Provider
Czech Science Foundation
OECD FORD
Applied mathematics
Solution period
01. 01. 2022 - 31. 12. 2024