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č
Uznané náklady
946 tis. Kč
Statní podpora
946 tis. Kč
0%
Poskytovatel
Grantová agentura České republiky
CEP
BA - Obecná matematika
Doba řešení
01. 01. 2008 - 31. 12. 2010