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”

Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti

Cíle projektu

Mnoho praktických algoritmických otázek má jádro založené na kombinatorických strukturách jako jsou grafy, orientované grafy či matroidy. Ačkoliv je typické, že na většinu těchto problémů nemáme žádná obecná efektivní algoritmická řešení, často jsme schopni je efektivně vyřešit pro všechny vstupy mající vhodnou vnitřní strukturu jako například omezenou šířku. Našim plánem je zkoumat a dále zobecnit užitečná obsáhlá využití strukturálních šířkových parametrů kombinatoriky (jako jsou stromová, větvená, kliková, DAG- či ranková šířka, které již všechny byly shledány velmi užitečnými) při navrhování nových efektivních parametrizovaných algoritmů, při řešení otázek rozhodnutelnosti logických teorií a dokazování nových strukturálních vět o kombinatorických objektech. Plán navazuje na náš předchozí obdobný úspěšný výzkum (zhruba od roku 2001).

Klíčová slova

tree-widthfixed parameter algorithmsgraph minorsgraph searchingcrossing number

Veřejná podpora

  • Poskytovatel

    Grantová agentura České republiky

  • Program

    Standardní projekty

  • Veřejná soutěž

    Standardní projekty 11 (SGA02008GA-ST)

  • Hlavní účastníci

  • Druh soutěže

    VS - Veřejná soutěž

  • Číslo smlouvy

    201/08/0308

Alternativní jazyk

  • Název projektu anglicky

    Utilization of structural and "Width" parameters in combinatorics and algorithmic complexity

  • Anotace anglicky

    Many practical algorithmic problems have a core based on combinatorial structures, such as graphs, digraphs, or matroids. Although it is typically infeasible to give general algorithmic solutions of (majority of) these problems, it is often the case thatsuch hard problems are indeed efficiently solvable for all inputs of certain internal structure like those having bounded width.Our research plan is to investigate and generalize the deep and interesting applications of structural width parameters in combinatorics (e.g. tree-width, branch-width, clique-width, DAG-width, or rank-width, which all have already proved to be very useful) to efficient parametrized algorithm design, decidability questions of theories in MSO logic, and new structural theorems about the underlying objects. This plan builds on our previous successful research (since about 2001) in the indicated directions.

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

    V - Vynikající výsledky projektu (s mezinárodním významem atd.)

  • Zhodnocení výsledků projektu

    V návrhu našeho projektu z roku 2007 byly nastíněny tyto tři hlavní směry vědeckého bádání: (1) výzkum strukturálních šířkových parametrů a dekompozic grafů a matroidů, (2) výzkum především algoritmických hledisek průsečíkového čísla grafů, (3) výzkum n?

Termíny řešení

  • Zahájení řešení

    1. 1. 2008

  • Ukončení řešení

    31. 12. 2010

  • Poslední stav řešení

    U - Ukončený projekt

  • Poslední uvolnění podpory

    16. 4. 2010

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

    CEP11-GA0-GA-U/03:3

  • Datum dodání záznamu

    9. 2. 2015

Finance

  • Celkové uznané náklady

    946 tis. Kč

  • Výše podpory ze státního rozpočtu

    946 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

946 tis. Kč

Statní podpora

946 tis. Kč

100%


Poskytovatel

Grantová agentura České republiky

CEP

BA - Obecná matematika

Doba řešení

01. 01. 2008 - 31. 12. 2010