Matthias Függer received his M.Sc. (2006) and his PhD (2010) in computer engineering from TU Wien, Austria. He is currently a post-doctoral researcher at LIX, Ecole polytechnique. His main research interest is the formal study of the fundamentals of computationally extremely restricted distributed devices manmade or models of natural systems). Specifically this includes (fault-tolerant) distributed algorithms in hardware and biology.
Link reversal is a versatile algorithm design paradigm, originally
proposed by Gafni and Bertsekas in 1981. The algorithms operate on
graphs, using local information only, to reverse some of a node's
incident links. Applications are in routing, mutual exclusion, leader
election, and resource allocation.
Although these algorithms are well-known, there have been only
preliminary results on time complexity, even for the simplest link
reversal algorithm for routing, called Full Reversal. Charron-Bost et
al. introduced a generalization, called LR, that includes Full
Reversal, and the more advanced Partial Reversal, as special cases.
In this talk an exact expression for the time complexity of LR is
presented. The expression is stated in terms of simple properties of
the initial graph. Having the exact formulas provides insight into the
behavior of Full and Partial Reversal on specific graph families.