Strukturální teorie grafů, složitost a parametrizované algoritmy

Mnoho praktických algoritmických otázek má své jádro založené na tradičních kombinatorických strukturách, jako jsou grafy, orientované grafy či matroidy. Pro efektivní algoritmické řešení těchto otázek je tudíž nezbytné porozumění těmto strukturám a relevantní teorii v diskrétní matematice. Náš tým se zabývá některými z nejnovějších výzkumných trendů v oblasti algoritmických aplikací diskrétní matematiky - strukturální teorie grafů, a logiky. Záběr výzkumu sahá od samotné matematické teorie přes výpočetní složitost po návrhy nových algoritmů.


Hlavní výzkumné priority

Pro podrobnější a aktuální popis výzkumných směrů odkazujeme na vlastní stránku, stránky členů týmu a na anglickou verzi. Zde stručně:

  • Šířkové a hloubkové strukturální parametry grafů a jiných struktur
  • Parametrizovaná složitost diskrétních problémů
  • Parametrizované algoritmy a kernelizace, metavěty a logické aspekty
  • Geometrické a topologické problémy grafů
  • Průsečíkové číslo grafu

Náš výzkumný tým je součástí širší Laboratoře Formela na FI MU a národního Centra excelence CE-ITI.


Informace pro studenty

Studentům se zájmem o popsané výzkumné směry nabízíme již od začátku studia jak

  • možnost se zapojit do vědeckého výzkumu na vysoké mezinárodní úrovni (majícím publikační výstupy ve špičových světových časopisech v oboru diskrétní matematiky a teoretické informatiky) a perspektivu pokračování studia a akademické dráhy v Ph.D. programu,

tak zároveň i možnosti

  • aplikačně orientované práce na konkrétních vývojových (převážně softwarových) projektech inspirovaných grafy a diskrétní matematikou.

Bližší informace je možné získat osobně od kteréhokoliv z členů naší skupiny, či se přímo nezávazně zapojit (a "ukázat") například

Studentům majícím zájem o naši výzkumnou oblast také doporučujeme návštěvu semináře FMDSA: Working Seminar on Formal Methods, Discrete Structures, and Algorithms.


Složení výzkumného týmu

(stav jaro 2014)

PhD studenti:
Ondrej Moriš, Jakub Gajarský, Marek Derňár, Tomáš Hebelka

Někteří dřívější studenti (nejen doktorští):
Robert Ganian (nyní TU Wien), Martin Derka (nyní student Univ. Waterloo), Matěj Klusáček, Jakub Mareček (nyní IBM research)


Řešené výzkumné projekty

(stav 2014)


Kontakt

[PH]
prof. RNDr. Petr Hliněný, Ph.D.
Email: hlineny(atsign)fi(dot)muni(dot)cz
http://www.fi.muni.cz/~hlineny/