Computing a graph's period quadratically by node condensation

DOI10.1016/0012-365X(73)90166-0zbMath0258.05114MaRDI QIDQ2559390

Yves Balcer, Arthur F. jun. Veinott

Publication date: 1973

Published in: Discrete Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Directed graphs (digraphs), tournaments (05C20) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

Orbits in max--min algebra, Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes, Computing matrix period in max--min algebra, On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product, Delay-induced discrete-time consensus, On the \(O(n^{3})\) algorithm for checking the strong robustness of interval fuzzy matrices, The robustness of interval fuzzy matrices, The robustness of interval matrices in max-plus algebra, Computing orbit period in max-min algebra, Linear matrix period in max-plus algebra, Computing periodic request functions to speed-up the analysis of non-cyclic task models, Max-algebraic attraction cones of nonnegative irreducible matrices, Orbits and critical components of matrices in max-min algebra, Matrix period in max-algebra, CSR expansions of matrix powers in max algebra, Powers of matrices over distributive lattices -- a review

Cites Work

• Unnamed Item
• Efficient determination of the transitive closure of a directed graph
• Scientific Applications: An algorithm for identifying the ergodic subchains and transient states of a stochastic matrix
• A transitive closure algorithm