Informace o projektu
Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti
- Kód projektu
- GA201/08/0308
- Období řešení
- 1/2008 - 12/2010
- Investor / Programový rámec / typ projektu
-
Grantová agentura ČR
- Standardní projekty
- Fakulta / Pracoviště MU
- Fakulta informatiky
- Klíčová slova
- stromová šířka, parametrizované algoritmy, minory grafů, prohledávání grafu, průsečíkové číslo
Mnoho praktických algoritmických otázek má jádro založené na kombinatorických strukturách jako jsou grafy či matroidy. Ačkoliv je typické, že na většinu těchto problémů nemáme žádná obecná efektivní algoritmická řešení, často jsme schopni je efektivně vyřešit pro všechny vstupy mající vhodnou vnitřní strukturu jako např. omezenou šířku.
Našim plánem je zkoumat a dále zobecnit užitečná obsáhlá využití strukturálních šířkových parametrů kombinatoriky (jako jsou stromová, větvená, kliková, DAG - či ranková šířka, které již všechny byly shledány velmi užitečnými) při navrhování nových efektivních parametrizovaných algoritmů, při řešení otázek rozhodnutelnosti logických teorií a dokazování nových strukturálních vět o kombinatorických objektech. Plán navazuje na náš předchozí obdobný úspěšný výzkum (zhruba od roku 2001).
Výsledky
Našim cílem je matematický výzkum strukturálních šířkových parametrů grafů, orientovaných grafů a matroidů (včetně dokazování vztažených teoretických výsledků) a jejich využití pro navrhování efektivních parametrizovaných algoritmů pro praktické těžké výpočetní problémy.
Publikace
Počet publikací: 24
2010
-
20 years of Negami's planar cover conjecture
Graphs and Combinatorics, rok: 2010, ročník: 26, vydání: 4, DOI
-
Algorithmic applications of linear rank-width
Rok: 2010, druh: Konferenční abstrakty
-
Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface
ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), rok: 2010
-
Are there any good digraph width measures?
Parameterized and exact computation, IPEC 2010, rok: 2010
-
Better algorithms for satisfiability problems for formulas of bounded rank-width
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), rok: 2010
-
Canonical generation of matroids
Rok: 2010, druh: Vyžádané přednášky
-
Česko-Slovenská Konference GRAFY 2010
Rok: 2010, druh: Uspořádání konference
-
New results on the complexity of oriented colouring on restricted digraph classes
SOFSEM 2010, Lecture Notes in Computer Science 5901, rok: 2010
-
On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
Discrete Applied Mathematics, rok: 2010, ročník: 158, vydání: 1
-
Proceedings of the 45th Czech-Slovak Conference GRAFY 2010
Rok: 2010, druh: Editorství tématického sborníku