Computing a Graph's Period Quadratically by Condensation.

A condensation algorithm for finding the period and cyclic classes of an n node strongly connected graph or equivalently, the period of an n state irreducible Markov chain is given for which an upper bound on the number of operations is proportional to Nsup2. This substantially improves upon the upper bounds of the two existing algorithms known to the authors, both of which are proportional to Nsup4. The idea of the authors method is this. The set of nodes accessible in one step from some node 1 say, belong to a common cyclic class and so can be condensed into a single node. Similarly, the set of nodes accessible in one step from that condensed node belong to a common cyclic class and so can be condensed into a single node. After at most 2n-2 repetitions of this procedure, the resulting graph is a circuit whose length is the period of the original graph and each of whose nodes is a condensation of a cyclic class in the original graph. Author