Informace o projektu
Structural properties, parameterized tractability and hardness in combinatorial problems
- Kód projektu
- GA17-00837S
- Období řešení
- 1/2017 - 12/2019
- Investor / Programový rámec / typ projektu
-
Grantová agentura ČR
- Standardní projekty
- Fakulta / Pracoviště MU
- Fakulta informatiky
The concept of parameterized tractability allows for guaranteed efficient solutions of some instances - as determined by the parameter, of problems which are intractable in their full generality. Our proposal addresses various questions belonging to theoretical foundations of parameterized algorithmics, namely those related to structural and topological graph theory, and to logic and interpretations in graphs. Among the problems we propose to investigate are algorithmic metatheorems for FO properties on dense graph classes, FO interpretations in sparse classes and their structural characterizations, parameterized tractability of graph crossing number and planar insertion problems, structural characterization of crossing-critical graphs, and other.
Publikace
Počet publikací: 15
2018
-
Deciding Parity of Graph Crossing Number
SIAM Journal on Discrete Mathematics, rok: 2018, ročník: 32, vydání: 3, DOI
-
FO model checking of geometric graphs
12th International Symposium on Parameterized and Exact Computation (IPEC 2017), rok: 2018
-
On Colourability of Polygon Visibility Graphs
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), rok: 2018
-
Parameterized Extension Complexity of Independent Set and Related Problems
Discrete Applied Mathematics, rok: 2018, ročník: 248, vydání: SI, DOI
2017
-
On upward straight-line embeddings of oriented paths
EGC 2017, XVII Spanish Meeting on Computational Geometry, rok: 2017