Strukturální vlastnosti a algoritmická složitost diskrétních problémů

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

Standardní projekty 8 (SGA02005GA-ST)

Hlavní účastníci

—

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

201/05/0050

Název projektu anglicky

Structural properties and algorithmic complexity of discrete problems

Anotace anglicky

Many practical algorithmic problems have a core based on the structures of discrete mathematics, like on graphs or matroids. It turns out that majority of the basic discrete problems are "almost unsolvable" (NP-hard) in their general formulation. Still,one has to look for, at least, approximate solutions to hard problems, or at solutions working under additional assumptions. The key to finding suitable assumptions allowing for effective solutions of hard problems lies in understanding their structure.As an example of a great success of structural approaches, we mention the deep and revolutionary Graph Minor Theory of Robertson and Seymour. Moreover, there is the new theory of parametrized complexity of algorithms by Downey and Fellows. The topic of our project is development of structural approaches to hard discrete problems, especially with emphasis on tree- or branch-width of graphs and matroids. Those include new applications of the structural methods in design of fixed parameter tractable

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 rámci řešení našeho projektu bylo objeveno množství nových teoretických poznatků v oblastech strukturálních a topologických vlastností kombinatorických struktur (především grafů a matroidů) a jejich algoritmických aplikacích. Tyto nové výsledky byly př

Zahájení řešení

1. 1. 2005

Ukončení řešení

31. 12. 2007

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

2. 5. 2007

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

CEP08-GA0-GA-U/04:3

Datum dodání záznamu

16. 12. 2008

Celkové uznané náklady

472 tis. Kč

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

453 tis. Kč

Ostatní veřejné zdroje financování

0 tis. Kč

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

28 tis. Kč