Title
Strukturální vlastnosti a algoritmická složitost diskrétních problémů
Code
GA201/05/0050
Summary
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,o ne 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 ofour project is development of structural approaches to hard discrete problems, especially with emphasis on tree- or branch-width of graphs and matroids.
Start year
2005
End year
2007
Provider
Grantová agentura ČR
Category
Obecná forma
Type
Standardní projekty
Solver
Information system of research, development and innovation (in Czech)