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 (16)

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

This page was built for publication: Computing a graph's period quadratically by node condensation