Generalizations of Bounds on the Index of Convergence to Weighted Digraphs
Preprint
Abstract
We study sequences of optimal walks of a growing length, in weighted digraphs, or equivalently, sequences of entries of max-algebraic matrix powers with growing exponents. It is known that these sequences are eventually periodic when the digraphs are strongly connected. The transient of such periodicity depends, in general, both on the size of digraph and on the magnitude of the weights. In this paper, we show that some bounds on the indices of periodicity of (unweighted) digraphs, such as the bounds of Wielandt, Dulmage-Mendelsohn, Schwarz, Kim and Gregory-Kirkland-Pullman, apply to the weights of optimal walks when one of their ends is a critical node.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Two cores of a nonnegative matrixLinear Algebra and its Applications, 2013
- New transience bounds for long walks in weighted digraphs2013
- Max-linear Systems: Theory and Algorithms2010
- On visualization scaling, subeigenvectors and Kleene stars in max algebraLinear Algebra and its Applications, 2009
- Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classesLinear Algebra and its Applications, 2009
- Wielandt's proof of the exponent inequality for primitive nonnegative matricesLinear Algebra and its Applications, 2002
- Powers of matrices over an extremal algebra with applications to periodic graphsMathematical Methods of Operations Research, 1997
- A bound on the exponent of a primitive matrix using Boolean rankLinear Algebra and its Applications, 1995
- The index set problem for Boolean (or nonnegative) matricesDiscrete Mathematics, 1993
- Unzerlegbare, nicht negative MatrizenMathematische Zeitschrift, 1950