Strukturální vlastnosti a algoritmická složitost diskrétních problémů
Cíle projektu
V pozadí mnoha praktických algoritmických problémů stojí struktury diskrétní matematiky, jako je graf nebo obecněji matroid. Jak se však ukazuje, většina již základních diskrétních problémů je "téměř neřešitelná" (NP-těžká) ve své obecné formulaci. Přesto je žádoucí hledat alespoň přibližná řešení takových těžkých problémů, nebo řešení fungující za dodatečných předpokladů. Klíčem k nalezení vhodných předpokladů umožňujících efektivní řešení těžkých problémů přitom je pochopení jejich vnitřní struktury.Jako příklad úspěchu tohoto strukturálního přístupu bychom zmínili hlubokou a převratnou teorii grafových minorů Robertsona a Seymoura. Mimo to je zde nová teorie parametrizované složitosti algoritmů Downeyho a Fellowse. Náplní našeho projektuje rozvíjení strukturálních přístupů k těžkým diskrétním problémům, zvláště s důrazem na stromovou či větvenou šířku grafů a matroidů. To zahrnuje nové aplikace strukturálních metod při vývoji parametrizovaně efektivních algoritmů na grafech, například
Klíčová slova
graphmatroidtree-widthclique-widthgraph minorscrossing numberparametrized complexity
Veřejná podpora
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
Alternativní jazyk
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
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 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ř
Termíny řešení
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
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
CEP08-GA0-GA-U/04:3
Datum dodání záznamu
16. 12. 2008
Finance
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č
Základní informace
Uznané náklady
472 tis. Kč
Statní podpora
453 tis. Kč
95%
Poskytovatel
Grantová agentura České republiky
CEP
BA - Obecná matematika
Doba řešení
01. 01. 2005 - 31. 12. 2007