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
2020
-
A New Perspective on FO Model Checking of Dense Graph Classes
ACM Transactions on Computational Logic, rok: 2020, ročník: 21, vydání: 4, DOI
-
Range assignment of base-stations maximizing coverage area without interference
Theoretical Computer Science, rok: 2020, ročník: 804, vydání: 1, DOI
-
Toroidal grid minors and stretch in embedded graphs
JOURNAL OF COMBINATORIAL THEORY SERIES B, rok: 2020, ročník: 140, vydání: 1, DOI
2019
-
Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12
35th International Symposium on Computational Geometry, SoCG 2019, rok: 2019
-
Drawing Bipartite Graphs in Two Layers with Specified Crossings
5th International Conference of Algorithms and Discrete Applied Mathematics (CALDAM 2019), rok: 2019
-
Exact Crossing Number Parameterized by Vertex Cover
GD 2019: Graph Drawing and Network Visualization, rok: 2019
-
FO model checking on geometric graphs
Computational geometry, rok: 2019, ročník: 78, vydání: 1, DOI
-
On conflict-free chromatic guarding of simple polygons
13th Annual International Conference on Combinatorial Optimization and Applications (COCOA'19), rok: 2019
-
On Degree Properties of Crossing-Critical Families of Graphs
Electronic Journal of Combinatorics, rok: 2019, ročník: 26, vydání: 1, DOI
2018
-
A Simpler Self-reduction Algorithm for Matroid Path-width
SIAM Journal on Discrete Mathematics, rok: 2018, ročník: 32, vydání: 2, DOI