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
2009
-
21 years of Negami's planar cover conjecture
Year: 2009, type:
-
Addendum to Matroid Tree-Width
European Journal of Combinatorics, year: 2009, volume: 30, edition: 4
-
Approximating the Crossing Number of Apex Graphs
Symposium Graph Drawing 2008, Lecture Notes in Computer Science, year: 2009
-
Better Polynomial Algorithms on Graphs of Bounded Rank-width.
IWOCA 2009: International Workshop On Combinatorial Algorithms, Lecture Notes in Computer Science 5874, year: 2009
-
On Digraph Width Measures in Parameterized Algorithmics
IWPEC 2009: International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science, year: 2009
-
The Parameterized Complexity of Oriented Colouring
MEMICS 2009 proceedings, year: 2009
2008
-
20 years of Negami's planar cover conjecture
20th Workshop on topological graph theory in Yokohama, year: 2008
-
20 years of Negami's planar cover conjecture
Year: 2008, type:
-
Approaching tree-width of graphs from matroidal perspective
Year: 2008, type:
-
Automata Approach to Graphs of Bounded Rank-width
International Workshop on Combinatorial Algorithms IWOCA 2008, year: 2008