Project information
Structure of tractable instances of hard algorithmic problems on graphs
- Project Identification
- GA20-04567S
- Project Period
- 1/2020 - 12/2022
- Investor / Pogramme / Project type
-
Czech Science Foundation
- Standard Projects
- MU Faculty or unit
-
Faculty of Informatics
- prof. RNDr. Petr Hliněný, Ph.D.
- RNDr. Deniz Agaoglu Cagirici, Ph.D.
- Onur Cagirici, M.Sc., Ph.D.
- doc. Mgr. Jan Obdržálek, PhD.
One of the fundamental questions in theoretical CS is how to approach problems which are intractable in their full generality. Our proposal is to investigate the internal structure of tractable instances of such generally hard problems on graphs, namely those dealing with structural and topological graph theory, geometric graphs, and of problems definable in various logics. In particular, we propose to investigate algorithmic and complexity theoretical aspects of new width and sparsity parameters of graph classes, properties of geometric representations of graphs, tractable instances for the FO model checking problem, and the detailed structure of the graph crossing number problem.
Sustainable Development Goals
Masaryk University is committed to the UN Sustainable Development Goals, which aim to improve the conditions and quality of life on our planet by 2030.
Publications
Total number of publications: 17
2023
-
Clique-Width of Point Configurations
Journal of Combinatorial Theory, Ser B, year: 2023, volume: 158, edition: 1, DOI
-
Efficient Isomorphism for Sd-Graphs and T-Graphs
ALGORITHMICA, year: 2023, volume: 85, edition: 2, DOI
-
Inserting Multiple Edges into a Planar Graph
Journal of Graph Algorithms and Applications, year: 2023, volume: 27, edition: 6, DOI
2022
-
Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12
COMBINATORICA, year: 2022, volume: 42, edition: 5, DOI
-
Graph Product Structure for h-Framed Graphs
33rd International Symposium on Algorithms and Computation (ISAAC 2022), year: 2022
-
Isomorphism Testing for T-graphs in FPT
WALCOM: Algorithms and Computation, year: 2022
-
Parameterised Partially-Predrawn Crossing Number
38th International Symposium on Computational Geometry (SoCG 2022), year: 2022
-
Twin-Width and Transductions of Proper k-Mixed-Thin Graphs
WG 2022: Graph-Theoretic Concepts in Computer Science, year: 2022
-
Weighted Model Counting with Twin-Width
25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022), year: 2022
2021
-
A Short Proof of Euler–Poincaré Formula
Extended Abstracts EuroComb 2021. Trends in Mathematics, year: 2021