
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 2n2 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