Project details


Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity

Project Identification:GA201/08/0308
Project Period:1/2008 - 12/2010
Investor:link to a new windowCzech Science Foundation
Programme / Project Type:Standard Projects -
MU Faculty/Unit:
Faculty of Informatics
MU Investigator:Prof. RNDr. Petr Hliněný, Ph.D.
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.