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í: 25
2008
-
Automata Approach to Graphs of Bounded Rank-width
International Workshop on Combinatorial Algorithms IWOCA 2008, rok: 2008
-
Finding branch-decomposition and rank-decomposition
SIAM Journal on Computing, rok: 2008, ročník: 38, vydání: 3
-
New infinite families of almost-planar crossing-critical graphs
Electronic Journal of Combinatorics, rok: 2008, ročník: 15, vydání: 1
-
Stars and Bonds in Crossing-Critical Graphs
Electronic Notes in Discrete Mathematics, rok: 2008, ročník: 31, vydání: 1
-
The crossing number of a projective graph is quadratic in the face--width
Electronic Journal of Combinatorics, rok: 2008, ročník: 15, vydání: 1