Project information
Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
- Project Identification
- GA14-03501S
- Project Period
- 1/2014 - 12/2016
- Investor / Pogramme / Project type
-
Czech Science Foundation
- Standard Projects
- MU Faculty or unit
-
Faculty of Informatics
- prof. RNDr. Petr Hliněný, Ph.D.
- Mgr. Marek Derňár
- RNDr. Jakub Gajarský, Ph.D.
- RNDr. Ondrej Moriš
- doc. Mgr. Jan Obdržálek, PhD.
Jeden z možných přístupů ke zdolání zdánlivě nepřekonatelné překážky NP-těžkosti algoritmických problémů nám podává teorie
parametrizované složitosti: Vstup těžkého problému je opatřen doplňkovým parametrem - libovolným číslem k, jehož jakákoliv počitatelná
funkce omezuje výpočetní složitost našeho problému. Snahou je volit parametr k tak, aby jeho hodnota byla na zajímavých vstupech nízká,
což následně umožňuje efektivní řešení problémů na takto charakterizovaných vstupech. V projektu budou hledány a studovány vhodné
strukturální a geometrické parametry pro třídy kombinatorických objektů (grafů) a nové poznatky budou využity v návrhu lepších
parametrizovaných algoritmů a obecných logikou popsaných tzv. algoritmických metavět. Mimo jiné bude pokračovat nedávno velmi úspěšné
nalézání dolních mezí parametrizované řešitelnosti problémů. Mezi novými směry výzkumu v navržené oblasti jsou především zmíněny
oblasti metavět pro kernelizaci (efektivní parametrické předzpracování) problémů a využití geometrických parametrů (vycházejících například
z reprezentace vstupního grafu).
Publications
Total number of publications: 15
2018
-
Parameterized Extension Complexity of Independent Set and Related Problems
Discrete Applied Mathematics, year: 2018, volume: 248, edition: SI, DOI
2017
-
A tighter insertion-based approximation of the crossing number
Journal of Combinatorial Optimization, year: 2017, volume: 33, edition: 4, DOI
-
First order limits of sparse graphs: Plane trees and path-width
Random Structures & Algorithms, year: 2017, volume: 50, edition: 4, DOI
-
Kernelization using structural parameters on sparse graph classes
Journal of Computer and System Sciences, year: 2017, volume: 84, edition: 1, DOI
2016
-
A New Perspective on FO Model Checking of Dense Graph Classes
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science LICS2016, year: 2016
-
Crossing Number is Hard for Kernelization
32nd International Symposium on Computational Geometry (SoCG 2016), year: 2016
-
Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs
Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548, year: 2016
-
The Crossing Number of the Cone of a Graph
Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, year: 2016
-
Tree-depth and Vertex-minors
European Journal of Combinatorics, year: 2016, volume: 56, edition: 1, DOI
2015
-
Faster Existential FO Model Checking on Posets
Logical Methods in Computer Science, year: 2015, volume: 11, edition: 4, DOI