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
- 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.
Publications
Total number of publications: 10
2022
-
Clique-Width of Point Configurations
Journal of Combinatorial Theory, Ser B, year: 2022, volume: 2021, DOI
-
Isomorphism Testing for T-graphs in FPT
Year: 2022
2021
-
A Short Proof of Euler–Poincaré Formula
Extended Abstracts EuroComb 2021. Trends in Mathematics, year: 2021
-
Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), year: 2021
-
On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees
Extended Abstracts EuroComb 2021. Trends in Mathematics, year: 2021
-
Twin-Width is Linear in the Poset Width
International Symposium on Parameterized and Exact Computation (IPEC), year: 2021
-
Unit Disk Visibility Graphs
Extended Abstracts EuroComb 2021, year: 2021
2020
-
Clique-Width of Point Configurations
Graph-Theoretic Concepts in Computer Science, WG 2020, year: 2020
-
Isomorphism Problem for Sd-Graphs
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), year: 2020
-
On Embeddability of Unit Disk Graphs onto Straight Lines
International Computer Science Symposium in Russia, CSR 2020, year: 2020