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 / Pogramme / Project type
-
Czech Science Foundation
- Standard Projects
- MU Faculty or 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
Publications
Total number of publications: 24
2008
-
Finding branch-decomposition and rank-decomposition
SIAM Journal on Computing, year: 2008, volume: 38, edition: 3
-
New infinite families of almost-planar crossing-critical graphs
Electronic Journal of Combinatorics, year: 2008, volume: 15, edition: 1
-
Stars and Bonds in Crossing-Critical Graphs
Electronic Notes in Discrete Mathematics, year: 2008, volume: 31, edition: 1
-
The crossing number of a projective graph is quadratic in the face--width
Electronic Journal of Combinatorics, year: 2008, volume: 15, edition: 1