Vše
Vše

Co hledáte?

Vše
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”
ME 418

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

graphclosurestructural property

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