Back to Search
Start Over
Generalizations of Bounds on the Index of Convergence to Weighted Digraphs
- Source :
- IEEE Conference on Decision and Control, IEEE Conference on Decision and Control, Dec 2014, Los Angeles, United States. ⟨10.1109/CDC.2014.7039627⟩, CDC
- Publication Year :
- 2013
-
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.<br />17 pages, 3 figures
- Subjects :
- Max algebra
Strongly connected component
Index (economics)
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Combinatorics
Index of convergence
Computer Science::Discrete Mathematics
Convergence (routing)
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
15A80, 15B48, 15A27, 15A21
Computer Science::Data Structures and Algorithms
Mathematics
Matrix powers
Mathematics::Combinatorics
Transient
Applied Mathematics
Digraph
weighted di-graphs
Directed graph
Nonnegative matrices
Optimal walks
Weighted digraphs
maximum walks
Combinatorics (math.CO)
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- IEEE Conference on Decision and Control, IEEE Conference on Decision and Control, Dec 2014, Los Angeles, United States. ⟨10.1109/CDC.2014.7039627⟩, CDC
- Accession number :
- edsair.doi.dedup.....d58fc8bccc922fd9f72647b9779d6ff9
- Full Text :
- https://doi.org/10.1109/CDC.2014.7039627⟩