Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity
|Project Period:||1/2008 - 12/2010|
|Investor:||Czech Science Foundation|
|Programme / Project Type:||Standard Projects -|
|Field:||BA - General mathematics (B - Physics and mathematics)|
IN - Informatics (I - Informatics)
|Keywords:||tree-width, fixed parameter algorithms, graph minors, graph searching, crossing number|
Many practical algorithmic problems have a core based on combinatorial structures, such as graphs, digraphs, or matroids. Although it is typically infeasible to give general algorithmic solutions of (majority of) these problems, it is often the case that such hard problems are indeed efficiently solvable for all inputs of certain internal stucture like those having bounded width.