Generalizations of bounds on the index of convergence to weighted digraphs

Glenn Merlet, Thomas Nowak, Hans Schneider, Sergey Sergeev

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)
875 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)121-134
JournalDiscrete Applied Mathematics
Volume178
Early online date24 Jul 2014
DOIs
Publication statusPublished - 11 Dec 2014

Keywords

  • Optimal walks
  • Max algebra
  • Nonnegative matrices
  • Matrix powers
  • Index of convergence
  • Transient
  • Weighted digraphs

Fingerprint

Dive into the research topics of 'Generalizations of bounds on the index of convergence to weighted digraphs'. Together they form a unique fingerprint.

Cite this