Informace o projektu
Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti
| Kód projektu | GA201/08/0308 CEP CORDIS MU WEB INET MU |
|---|---|
| Doba řešení | 01.01.2008–31.12.2010 |
| Stav | ukončený |
| Investor | Grantová agentura ČR |
| Program | Standardní projekty |
| Řešitel za FI |
Anotace
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).
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).