Project information

Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity

Project Identification
GA201/08/0308
Project Period
1/2008 - 12/2010
Investor
Czech Science Foundation
Programme / Project Type
Standard Projects
MU Faculty/Unit
Faculty of 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.

Results Only in Czech

Našim cílem je matematický výzkum strukturálních šířkových parametrů grafů, orientovaných grafů a matroidů (včetně dokazování vztažených teoretických výsledků) a jejich využití pro navrhování efektivních parametrizovaných algoritmů pro praktické těžké výpočetní problémy.

You are running an old browser version. We recommend updating your browser to its latest version.

More info