Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872188 | Discrete Applied Mathematics | 2014 | 14 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Glenn Merlet, Thomas Nowak, Hans Schneider, SergeÄ Sergeev,