Accession Number : AD0737641

Title :   Computing a Graph's Period Quadratically by Condensation.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF OPERATIONS RESEARCH

Personal Author(s) : Balcer,Yves ; Veinott,Arthur F. , Jr

Report Date : 23 NOV 1971

Pagination or Media Count : 18

Abstract : 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)

Descriptors :   (*STOCHASTIC PROCESSES, GRAPHICS), SET THEORY, MATRICES(MATHEMATICS), THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE