Titre : The Transience of Long Walks
Exposant : Thomas Novak
Résumé : What are the lengths of walks between two given vertices in a graph?
It turns out that the set of possible lengths has a periodic behavior after an initial
transient phase. The study of this transient phase has been ongoing research
from the '50s until today. Quite a number of results involving certain graph parameters are available.
More generally, one can ask for the maximum weight of walks between two
vertices with a given length in a weighted digraph. The answer, while
computationally easy, also shows a periodic behavior. The analytic study of
this more general case has many applications, e.g., in manufacturing systems,
cyclic scheduling, and some distributed algorithms.
It gives guidelines for designing such systems in a way that optimizes performance.
This talk gives an overview of results on this transient behavior of walks in
(weighted) digraphs.