An optimal algorithm for the period of a strongly connected digraph (Q1209368)

This paper presents a simple modification of the breadth-first search for the single-source shortest paths problem that allows the computation of the period in an optimal fashion: \(O(| E|)\) time and space. Moreover, the constants hidden by the \(O(\cdot)\) notation are small, so the proposed algorithm turns out to be very efficient on strongly connected digraphs of any size. The interest in the period --- a seemingly strange quantity --- arises from the theory of non-negative irreducible matrices and its applications, e.g. spectral and structural properties of graphs, long-term behaviour of non-negative discrete time dynamical systems, Markov chains, etc.