Speciální grafové, hypergrafové a algoritmické struktury
Cíle projektu
V projektu budou metodami soudobé diskrétní matematiky a informatiky studovány vybrané grafové, hypergrafové, algoritmické a datové struktury. Hlavním cílem je získat nové poznatky základního výzkumu a odpovídajícím způsobem (publikace v časopisech a vystoupení na konferencích) je prezentovat na mezinárodní úrovni. V první řadě budeme řešit problémy grafové a hypergrafové, s užším zaměřením na vhodné modely komunikačních sítí a možné aplikační výstupy, zejména pro paralelní výpočty. Budou studovány mj.hyperkrychle a jejich zobecnění, Cayleyho grafy a vrcholově tranzitivní grafy obecně. Chceme se zabývat vzájemnými vztahy různých (výše uvedených, ale i dalších) tříd grafů (vnořitelnost), konstrukcí efektivních algoritmů pro řešení odpovídajících grafových a hypergrafových úloh (včetně analýzy jejich složitostí a návrhu vhodných datových struktur) a obecněji i vlastnostmi a vztahy různých tříd kombinatorických a algoritmických problémů.
Klíčová slova
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
—
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta
Druh soutěže
—
Číslo smlouvy
—
Alternativní jazyk
Název projektu anglicky
Special graph, hypergraph and algorithmic structures
Anotace anglicky
The project involves study selected graph, hypergraoh, algorithmic and data structures, using contemporary methods of discrete mathematics. The main goal is to obtain new results of basic research and to present them on an international level (publications in research journals, conference talks). We shall primarily deal with graph and hypergraph problems, with special regards to suitable models of interconnection networks and possible aplications, in particular, in parallel computing. We intend to investigate relationships between various (above mentioned and also other) classes of graphs (embeddability), to construct efficient algorithms for corresponding graph and hypergraph problems (including analysis of their complexity and the desing of appropriate data structures) and to study properties of various classes of combinatorial and algorithmic problems and their relationships.
Vědní obory
Kategorie VaV
—
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory
(dle převodníku)10101 - Pure mathematics
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
Jedná se o velký projekt z teorie grafů. Výsledkem je 47 článků, z nich celá řada již byla publikována nebo přijata k publikaci v předních světových časopisech. Projekt velmi úspěšně přispěl k aktuálnímu výzkumu v dané oblasti. Údaje jsou adekvátní. Proj
Termíny řešení
Zahájení řešení
1. 1. 1998
Ukončení řešení
1. 1. 2000
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
—
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
CEP/2001/GA0/GA01GA/U/N/9:4
Datum dodání záznamu
—
Finance
Celkové uznané náklady
1 237 tis. Kč
Výše podpory ze státního rozpočtu
1 077 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Uznané náklady
1 237 tis. Kč
Statní podpora
1 077 tis. Kč
0%
Poskytovatel
Grantová agentura České republiky
CEP
BA - Obecná matematika
Doba řešení
01. 01. 1998 - 01. 01. 2000