Computing a graph's period quadratically by node condensation

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

Arthur F. jun. Veinott, Yves Balcer

Publication date: 1973

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

Mathematics Subject Classification ID

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

05C20: Directed graphs (digraphs), tournaments

05-04: Software, source code, etc. for problems pertaining to combinatorics

Related Items

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

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