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
2010
-
20 years of Negami's planar cover conjecture
Graphs and Combinatorics, year: 2010, volume: 26, edition: 4, DOI
-
Algorithmic applications of linear rank-width
Year: 2010, type: Conference abstract
-
Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface
ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), year: 2010
-
Are there any good digraph width measures?
Parameterized and exact computation, IPEC 2010, year: 2010
-
Better algorithms for satisfiability problems for formulas of bounded rank-width
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), year: 2010
-
Canonical generation of matroids
Year: 2010, type:
-
Česko-Slovenská Konference GRAFY 2010
Year: 2010, type: Conference
-
New results on the complexity of oriented colouring on restricted digraph classes
SOFSEM 2010, Lecture Notes in Computer Science 5901, year: 2010
-
On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
Discrete Applied Mathematics, year: 2010, volume: 158, edition: 1
-
Proceedings of the 45th Czech-Slovak Conference GRAFY 2010
Year: 2010, type: