Structural properties and algorithmic complexity of discrete problems
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 8 (SGA02005GA-ST)
Main participants
—
Contest type
VS - Public tender
Contract ID
201/05/0050
Alternative language
Project name in Czech
Strukturální vlastnosti a algoritmická složitost diskrétních problémů
Annotation in Czech
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
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
IN - Informatics
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</a>)
10101 - Pure mathematics<br>10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
During research on our grant project we have found out many new theoretical results in the areas of structural and topological properties of combinatorial structures (mainly of graphs and matroids), and of their algorithmic applications. These new statem
Solution timeline
Realization period - beginning
Jan 1, 2005
Realization period - end
Dec 31, 2007
Project status
U - Finished project
Latest support payment
May 2, 2007
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP08-GA0-GA-U/04:3
Data delivery date
Dec 16, 2008
Finance
Total approved costs
472 thou. CZK
Public financial support
453 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
28 thou. CZK