Generalizations of Bounds on the Index of Convergence to Weighted Digraphs

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.

17 pages, 3 figures

References in corpus (5)

• On visualisation scaling, subeigenvectors and Kleene stars in max algebra
• CSR expansions of matrix powers in max algebra
• Two cores of a nonnegative matrix
• New Transience Bounds for Long Walks
• Fiedler-Ptak scaling in max algebra

Cited by in corpus (4)

• Reachability of eigenspaces for interval circulant matrices in max-algebra
• On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product
• Algorithm for the CSR expansion of max-plus matrices using the characteristic polynomial
• New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank