Project information
Well-structured combinatorial classes, width parameters, and design of efficient algorithms
- Project Identification
- GAP202/11/0196
- Project Period
- 1/2011 - 12/2013
- Investor / Pogramme / Project type
-
Czech Science Foundation
- Standard Projects
- MU Faculty or unit
- Faculty of Informatics
- Cooperating Organization
-
University of West Bohemia in Pilsen
Našim cílem je dále rozvíjet teoretické poznatky strukturální kombinatoriky, především o tzv. šířkových parametrech, a hledat jejich nové úspěšné aplikace v návrhu efektivních algoritmů pro těžké problémy.
Za tímto účelem nově spojíme síly a dosavadní výsledky navrhovatele a spolunavrhovatele.
Publications
Total number of publications: 18
2014
-
Lower Bounds on the Complexity of MSO_1 Model-Checking
Journal of Computer and System Sciences, year: 2014, volume: 80, edition: 1, DOI
2013
-
Better algorithms for satisfiability problems for formulas of bounded rank-width
Fundamenta Informaticae, year: 2013, volume: 123, edition: 1, DOI
-
Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes
Combinatorial Algorithms 24th International Workshop, IWOCA 2013, year: 2013
-
FO Model Checking of Interval Graphs
ICALP (2) 2013, year: 2013
-
Kernelization Using Structural Parameters on Sparse Graph Classes
ESA 2013, year: 2013
-
Parameterized Algorithms for Modular-Width
Parameterized and Exact Computation, year: 2013
-
Unified Approach to Polynomial Algorithms on Graphs of Bounded (bi-)Rank-width
European Journal of Combinatorics, year: 2013, volume: 34, edition: 3, DOI
2012
-
Can dense graphs be "sparse"?
Year: 2012, type: Conference abstract
-
Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), year: 2012
-
Faster than Courcelle's theorem on shrubs
Year: 2012, type: