Strukturální teorie grafů a parametrizovaná složitost

Poskytovatel

Grantová agentura České republiky

Program

Mezinárodní projekty

Veřejná soutěž

Mezinárodní projekty 3 (SGA02009GA1GC)

Hlavní účastníci

—

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

201/09/J021

Název projektu anglicky

Structural graph theory and parameterized complexity

Anotace anglicky

Many real-world algorithmic problems turn out to be intractable in their full generality. Theory of parameterized complexity, however, provides a useful framework for a refined analysis of such hard problems, and for designing conceptually new algorithmsthat can solve hard problems for the real-world instances efficiently. In contrast to heuristics, this approach provides guarantied runtime bounds.Graphs are combinatorial structures suitable for modeling many discrete and optimization problems. Structural graph theory has already proved very useful in parameterized algorithmics. For instance, most of traditional hard problems are efficiently solvable on graphs of bounded tree-width. We plan to exploit other structural properties of graphs like branch-width, DAG-width, rank-width, or their topological properties. Our goal is to find new application areas of structural graph theory in parameterized algorithm design, by collaboration of our research groups from both areas.

Kategorie VaV

ZV - Základní výzkum

CEP - hlavní obor

IN - Informatika

CEP - vedlejší obor

BA - Obecná matematika

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

Dosažené výsledky jsou následující: Za prvé jsme podali komplexní přehled parametrizované složitosti řešení známých grafových problému pro orientované grafy vzhledem ke&nbsp; známým strukturálním mírám (?šířkám?).&nbsp; Navíc jsme ukázali, že většina tě?

Zahájení řešení

1. 1. 2009

Ukončení řešení

31. 12. 2010

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

16. 4. 2010

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-GC-U/03:3

Datum dodání záznamu

9. 2. 2015

Celkové uznané náklady

1 014 tis. Kč

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

1 014 tis. Kč

Ostatní veřejné zdroje financování

0 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč