Project information
Structural properties, parameterized tractability and hardness in combinatorial problems
- Project Identification
- GA17-00837S
- Project Period
- 1/2017 - 12/2019
- Investor / Pogramme / Project type
-
Czech Science Foundation
- Standard Projects
- MU Faculty or unit
- Faculty of Informatics
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.
Publications
Total number of publications: 15
2020
-
A New Perspective on FO Model Checking of Dense Graph Classes
ACM Transactions on Computational Logic, year: 2020, volume: 21, edition: 4, DOI
-
Range assignment of base-stations maximizing coverage area without interference
Theoretical Computer Science, year: 2020, volume: 804, edition: 1, DOI
-
Toroidal grid minors and stretch in embedded graphs
JOURNAL OF COMBINATORIAL THEORY SERIES B, year: 2020, volume: 140, edition: 1, DOI
2019
-
Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12
35th International Symposium on Computational Geometry, SoCG 2019, year: 2019
-
Drawing Bipartite Graphs in Two Layers with Specified Crossings
5th International Conference of Algorithms and Discrete Applied Mathematics (CALDAM 2019), year: 2019
-
Exact Crossing Number Parameterized by Vertex Cover
GD 2019: Graph Drawing and Network Visualization, year: 2019
-
FO model checking on geometric graphs
Computational geometry, year: 2019, volume: 78, edition: 1, DOI
-
On conflict-free chromatic guarding of simple polygons
13th Annual International Conference on Combinatorial Optimization and Applications (COCOA'19), year: 2019
-
On Degree Properties of Crossing-Critical Families of Graphs
Electronic Journal of Combinatorics, year: 2019, volume: 26, edition: 1, DOI
2018
-
A Simpler Self-reduction Algorithm for Matroid Path-width
SIAM Journal on Discrete Mathematics, year: 2018, volume: 32, edition: 2, DOI