BARC talk by Loukas Georgiadis

Thursday, 31 October 2019, Loukas Georgiadis, Associate Professor at the University of Ioannina, Greece, will give a talk on "Dynamic Dominators, Low-High Orders, and Related Problems".

Title:
On Dynamic Dominators, Low-High Orders, and Related Problems

Abstract:
Computing dominators is a crucial first step in global code optimization and has many applications in other diverse areas. The dominator relation in a directed graph G with a designated start vertex s is represented by the dominator tree D of G, such that v dominates w if and only if v is an ancestor of w in D. A low-high order is a preorder of D that certifies the correctness of the dominator tree. In this talk, we first describe some applications of low-high orders in connectivity and fault-tolerant network design problems. Then, we consider the problem of maintaining dynamically the dominator tree and a low-high order of a directed graph that undergoes edge updates. We describe algorithms that achieve O(mn) total update time using O(n) space for the incremental (insertions only) case in general directed graphs and for the decremental (deletions only) case in directed acyclic graphs, where n is the number of vertices and m is the number of edges (after all insertions in the incremental case and before any deletion in the decremental case). For the decremental problem in general directed graphs, we give an algorithm with O(mn logn) total update and O(n^2 log n) space. We also provide a conditional lower bound that gives evidence that these running times may be tight up to subpolynomial factors.

Bio:
Loukas Georgiadis obtained his Ph.D. at Princeton University while working with Robert E. Tarjan in the area of design and analysis of algorithms and data structures. After obtaining his Ph.D. he has worked as a researcher at the University of Aarhus and at the Hewlett-Packard Laboratories (Palo Alto, CA), and as an Assistant Professor at the University of Western Macedonia. Since 2012 he joined the University of Ioannina where he currently is an Associate Professor. Loukas' research interests include the design and analysis of algorithms and data structures, implementation and experimental study of algorithms and data structures, graph algorithms, computational geometry, and combinatorial optimization.