Informace o projektu
Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
- Kód projektu
- GA14-03501S
- Období řešení
- 1/2014 - 12/2016
- Investor / Programový rámec / typ projektu
-
Grantová agentura ČR
- Standardní projekty
- Fakulta / Pracoviště MU
-
Fakulta informatiky
- 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).
Publikace
Počet publikací: 15
2018
-
Parameterized Extension Complexity of Independent Set and Related Problems
Discrete Applied Mathematics, rok: 2018, ročník: 248, vydání: SI, DOI
2017
-
A tighter insertion-based approximation of the crossing number
Journal of Combinatorial Optimization, rok: 2017, ročník: 33, vydání: 4, DOI
-
First order limits of sparse graphs: Plane trees and path-width
Random Structures & Algorithms, rok: 2017, ročník: 50, vydání: 4, DOI
-
Kernelization using structural parameters on sparse graph classes
Journal of Computer and System Sciences, rok: 2017, ročník: 84, vydání: 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, rok: 2016
-
Crossing Number is Hard for Kernelization
32nd International Symposium on Computational Geometry (SoCG 2016), rok: 2016
-
Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs
Mathematical and Engineering Methods in Computer Science, Lecture Notes in Computer Science 9548, rok: 2016
-
The Crossing Number of the Cone of a Graph
Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, rok: 2016
-
Tree-depth and Vertex-minors
European Journal of Combinatorics, rok: 2016, ročník: 56, vydání: 1, DOI
2015
-
Faster Existential FO Model Checking on Posets
Logical Methods in Computer Science, rok: 2015, ročník: 11, vydání: 4, DOI