Generalizations of bounds on the index of convergence to weighted digraphs
From MaRDI portal
(Redirected from Publication:741541)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5065241 (Why is no real title available?)
- scientific article; zbMATH DE number 2221679 (Why is no real title available?)
- A bound on the exponent of a primitive matrix using Boolean rank
- An extension of the Dulmage-Mendelsohn theorem
- CSR expansions of matrix powers in max algebra
- Combinatorial matrix theory
- Diagonally dominant matrices
- Fiedler-Pták scaling in max algebra
- Gaps in the exponent set of primitive matrices
- Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
- Max-linear systems. Theory and algorithms.
- On a sharp estimation in the theory of binary relations on a finite set
- On the index of convergence of an irreducible Boolean matrix
- On visualization scaling, subeigenvectors and Kleene stars in max algebra
- Periods of Connected Networks and Powers of Nonnegative Matrices
- Powers of matrices over an extremal algebra with applications to periodic graphs
- The index set problem for Boolean (or nonnegative) matrices
- Transience bounds for long walks
- Two cores of a nonnegative matrix
- Unzerlegbare, nicht negative Matrizen
- Wielandt's proof of the exponent inequality for primitive nonnegative matrices
Cited in
(13)- Lifespan in a primitive Boolean linear dynamical system
- An upper bound of Brualdi-Ross type for the indices of convergence of digraphs
- scientific article; zbMATH DE number 7670358 (Why is no real title available?)
- New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank
- A bound for the rank-one transient of inhomogeneous matrix products in special case.
- An expansion property of Boolean linear maps
- Transience bounds for long walks
- scientific article; zbMATH DE number 851021 (Why is no real title available?)
- Note on indices of convergence of digraphs.
- scientific article; zbMATH DE number 147637 (Why is no real title available?)
- On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers
- 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
This page was built for publication: Generalizations of bounds on the index of convergence to weighted digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q741541)
