Přejít k obsahu | Přejít k hlavnímu menu | Přejít k vyhledávání

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

Informace

Projekt nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka projektu je na webu muni.cz.
Logo poskytovatele
Kód projektu
GA201/08/0308
Období řešení
1/2008 - 12/2010
Investor / Programový rámec / typ projektu
Grantová agentura ČR
  • Standardní projekty
Fakulta / Pracoviště MU
Fakulta informatiky
Klíčová slova
stromová šířka, parametrizované algoritmy, minory grafů, prohledávání grafu, průsečíkové číslo

Mnoho praktických algoritmických otázek má jádro založené na kombinatorických strukturách jako jsou 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ř. 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).

Výsledky

Našim cílem je matematický výzkum strukturálních šířkových parametrů grafů, orientovaných grafů a matroidů (včetně dokazování vztažených teoretických výsledků) a jejich využití pro navrhování efektivních parametrizovaných algoritmů pro praktické těžké výpočetní problémy.

Publikace

Počet publikací: 25

2010

Předchozí 1 2 3 Další

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info