Strukturální vlastnosti grafů a tříd grafů
Cíle projektu
Výzkum bude soustředěn na studium strukturálních vlastností grafů, náležejících do některých důležitých algoritmicky efektivně rozpoznatelných tříd, zejména do tříd majících vztah k algoritmicky velmi obtížným (NP-úplným) problémům. Důležitost tohoto směru výzkumu spočívá především v tom, že ve vhodně zvolených třídách grafů se mnohé NP-úplné problémy stávají algoritmicky efektivně řešitelnými. Navrhovaný směr výzkumu poskytuje algoritmicky efektivně ověřitelné podmínky pro NP-těžké grafové vlastnosti aparametry. Výsledky tohoto typu jsou často prvními kroky k nalezení efektivních algoritmů pro dané problémy.
Klíčová slova
Veřejná podpora
Poskytovatel
Ministerstvo školství, mládeže a tělovýchovy
Program
KONTAKT
Veřejná soutěž
KONTAKT 1 (SMSM200132001)
Hlavní účastníci
Západočeská univerzita v Plzni / Fakulta aplikovaných věd
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
—
Alternativní jazyk
Název projektu anglicky
Structural properties of graphs and graph classes
Anotace anglicky
The research will be focused on studying structural properties of graphs from some important algorithmically efficiently recognizable classes of graphs, especially on those that are related to some algorithmically very difficult (NP-hard) problems. The importance of this direction of research is given by the fact that in such subclasses many NP-hard problems become efficiently algorithmically solvable. The proposed direction of research gives algorithmically efficiently verifiable sufficient conditionsfor NP-hard properties and parameters of graphs. Results of this type often are starting points for efficient algorithmic solutions.
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
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Spolupráce v diskrétní matematice-teorii grafů - systémy hranově disjunktních cest v lokálně souvislých grafech
Termíny řešení
Zahájení řešení
1. 1. 2001
Ukončení řešení
1. 1. 2003
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/2004/MSM/MSM4ME/U/N/4:2
Datum dodání záznamu
3. 6. 2008
Finance
Celkové uznané náklady
402 tis. Kč
Výše podpory ze státního rozpočtu
190 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
179 tis. Kč
Základní informace
Uznané náklady
402 tis. Kč
Statní podpora
190 tis. Kč
47%
Poskytovatel
Ministerstvo školství, mládeže a tělovýchovy
CEP
BA - Obecná matematika
Doba řešení
01. 01. 2001 - 01. 01. 2003