Název projektu
Speciální grafové, hypergrafové a algoritmické struktury
Kód
GA201/98/1451
Řešitel
Rok zahájení
1998
Rok ukončení
2000
Poskytovatel
Grantová agentura ČR
Kategorie
Obecná forma
Typ
Standardní projekty
Předmět výzkumu
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 vys toupení 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ů.
Informační systém výzkumu, vývoje a inovací