Reprezentace grafů
Cíle projektu
Reprezentací grafu nazýváme přiřazení objektů z dané množiny vrcholům grafu takovým způsobem, že z informace o přiřazených objektech je možno zpětně získat strukturu původního grafu. Vrcholům populárních intervalových grafů například můžeme přiřadit intervaly na přímce tak, že hrany grafu odpovídají přesně dvojicím protínajících se intervalů. Reprezentace grafů mají mnoho použití v informatice a operačním výzkumu, a v dnešní době je to důležitá a velmi zkoumaná oblast teorie grafů. Cílem tohoto projektuje vývoj metod použitelných v teorii grafových reprezentací a celkově v kombinatorice, jakožto i řešení několika konkrétních problémů. Tyto problémy se týkají variant produktové dimenze a dvojitého konkurenčního čísla, různých druhů průnikových reprezentací, a příbuzných otázek o barvení grafu. Na některých z těchto problémů aktivně spolupracuji se zahraničními institucemi, a máme již částečné výsledky.
Klíčová slova
graphrepresentationsproductdimensionintersectionrepresentationdoublecompetitionnumber
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Postdoktorandské granty
Veřejná soutěž
Postdoktorandské granty 12 (SGA02012GA1PD)
Hlavní účastníci
—
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
P201-12-P288
Alternativní jazyk
Název projektu anglicky
Graph representations
Anotace anglicky
A graph representation is a correspondence between the vertices of a graph and a family of sets of a given kind such that the information about the sets allows us to retrieve the structure of the graph. The vertices of the extensively investigated interval graphs, for instance, can be represented by intervals on the real line in such a way that two intervals intersect if and only if the corresponding vertices are adjacent. Graph representations have many applications in computer science and operations research, and are an important and well-researched topic nowadays. The objective of this project is to broaden the repertoire of techniques used in the area of graph representations and in combinatorics at large, as well as to solve several specific problems. These problems concern variations of product dimension, double competition number, several versions of intersection representations, and a related graph coloring problem. Some of these problems are the object of my active collaboration with foreigninstitutions, and we already have some partial results regarding them.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
IN - Informatika
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory
(dle převodníku)10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
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
Přestože se řešitelka výrazně odchýlila od původních cílů stanovených v návrhu projektu, jsou dosažené výsledky hodnotným příspěvkem k zajímavým otázkám souvisejícím s reprezentacemi grafů a jsou v souladu se záměrem projektu. Výstupem projektu jsou 2 p?
Termíny řešení
Zahájení řešení
1. 1. 2012
Ukončení řešení
31. 12. 2015
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
10. 4. 2015
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
CEP16-GA0-GP-U/01:1
Datum dodání záznamu
6. 5. 2016
Finance
Celkové uznané náklady
1 309 tis. Kč
Výše podpory ze státního rozpočtu
1 309 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Základní informace
Uznané náklady
1 309 tis. Kč
Statní podpora
1 309 tis. Kč
100%
Poskytovatel
Grantová agentura České republiky
CEP
BA - Obecná matematika
Doba řešení
01. 01. 2012 - 31. 12. 2015