Generalizations of bounds on the index of convergence to weighted digraphs

DOI10.1016/J.DAM.2014.06.026zbMATH Open1300.05121arXiv1307.3716OpenAlexW2160736732MaRDI QIDQ741541FDOQ741541

Authors: Glenn Merlet, Thomas Nowak, Hans Schneider, Sergey M. Sergeev 

Publication date: 12 September 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1307.3716

Recommendations

• Note on indices of convergence of digraphs.
• scientific article; zbMATH DE number 2147943
• Transience bounds for long walks
• Generalized indices of non-primitive graphs
• scientific article; zbMATH DE number 147637

zbMATH Keywords

transientnonnegative matricesweighted digraphsmatrix powersmax algebraindex of convergenceoptimal walks

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22) Random walks on graphs (05C81)

Cites Work

• Max-linear systems. Theory and algorithms.
• Fiedler-Pták scaling in max algebra
• Combinatorial matrix theory
• Title not available (Why is that?)
• On visualization scaling, subeigenvectors and Kleene stars in max algebra
• Title not available (Why is that?)
• Unzerlegbare, nicht negative Matrizen
• Periods of Connected Networks and Powers of Nonnegative Matrices
• An extension of the Dulmage-Mendelsohn theorem
• Gaps in the exponent set of primitive matrices
• Powers of matrices over an extremal algebra with applications to periodic graphs
• Transience bounds for long walks
• CSR expansions of matrix powers in max algebra
• Diagonally dominant matrices
• On the index of convergence of an irreducible Boolean matrix
• On a sharp estimation in the theory of binary relations on a finite set
• Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes
• A bound on the exponent of a primitive matrix using Boolean rank
• The index set problem for Boolean (or nonnegative) matrices
• Wielandt's proof of the exponent inequality for primitive nonnegative matrices
• Two cores of a nonnegative matrix

Cited In (13)

• Lifespan in a primitive Boolean linear dynamical system
• A bound for the rank-one transient of inhomogeneous matrix products in special case
• An upper bound of Brualdi-Ross type for the indices of convergence of digraphs
• Title not available (Why is that?)
• New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank
• An expansion property of Boolean linear maps
• Transience bounds for long walks
• Title not available (Why is that?)
• Note on indices of convergence of digraphs.
• Title not available (Why is that?)
• 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)