Přednáška pro odbornou veřejnost v rámci habilitačního řízení
Vážení,
jménem předsedy habilitační komise prof. Kozubka si Vás dovoluji pozvat na přednášku pro odbornou veřejnost v rámci habilitačního řízení Mgr. Jana Obdržálka, PhD., FI MU.
Název přednášky: Digraph Width Measures
Abstrakt: Treewidth, defined by Robertson and Seymour, proved to be an extremely successful graph parameter. Intuitively, it measures how much tree-like a given graph is. Many problems which are NP-hard on general graphs become tractable on graphs of low treewidth. However treewidth quickly hits its limits once we try to apply it to directed graphs. Directed acyclic graphs (DAGs), on which many problems have simple efficient algorithms, can have arbitrarily high treewidth. Naturally one can ask whether there is a digraph width measure with all the nice properties of treewidth. In this talk we first quickly survey some of the known digraph width measures, and then try to answer the question whether there indeed is a good directed counterpart to treewidth.
Přednáška bude proslovena v úterý 3. října 2017 v posluchárně D2 od 14 hod.
Všichni zájemci jsou srdečně zváni.
jménem předsedy habilitační komise prof. Kozubka si Vás dovoluji pozvat na přednášku pro odbornou veřejnost v rámci habilitačního řízení Mgr. Jana Obdržálka, PhD., FI MU.
Název přednášky: Digraph Width Measures
Abstrakt: Treewidth, defined by Robertson and Seymour, proved to be an extremely successful graph parameter. Intuitively, it measures how much tree-like a given graph is. Many problems which are NP-hard on general graphs become tractable on graphs of low treewidth. However treewidth quickly hits its limits once we try to apply it to directed graphs. Directed acyclic graphs (DAGs), on which many problems have simple efficient algorithms, can have arbitrarily high treewidth. Naturally one can ask whether there is a digraph width measure with all the nice properties of treewidth. In this talk we first quickly survey some of the known digraph width measures, and then try to answer the question whether there indeed is a good directed counterpart to treewidth.
Přednáška bude proslovena v úterý 3. října 2017 v posluchárně D2 od 14 hod.
Všichni zájemci jsou srdečně zváni.
- Webová adresa