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

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.

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 <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)
10101 - Pure mathematics<br>10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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?

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

Podobné projekty(10)