65
Views
1
CrossRef citations to date
0
Altmetric
Research Article

On the tightness of bounds for transients of weak CSR expansions and periodicity transients of critical rows and columns of tropical matrix powers

, &
Pages 4320-4350 | Received 29 Aug 2018, Accepted 24 Dec 2020, Published online: 03 Feb 2021

References

  • Butkovič P. Max-linear systems: theory and algorithms. London: Springer; 2010.
  • Cohen G, Dubois D, Quadrat J-P, et al. Analyse du comportement périodique de systèmes de production par la théorie des dioïdes. Le Chesnay: INRIA; 1983. (Rapport de Recherche no. 191).
  • Hartmann M, Arguelles C. Transience bounds for long walks. Math Oper Res. 1999;24(2):414–439.
  • Bouillard A, Gaujal B. Coupling time of a (max, plus) matrix. Proceedings of the workshop on max-plus algebra at the 1st ifac symposium on system structure and control; Amsterdam: Elsevier; 2001, p. 335–400.
  • Soto y Koelemeijer G. On the behaviour of classes of min-max-plus systems [Ph.D. thesis]. Delft University of Technology; 2003.
  • Akian M, Gaubert S, Walsh C. Discrete max-plus spectral theory. In: Litvinov GL, Maslov VP, editors, Idempotent mathematics and mathematical physics. Vol. 377, Contemporary Mathematics; Providence (RI): AMS; 2005. p. 53–77.
  • Charron-Bost B, Függer M, Nowak T. New transience bounds for max-plus linear systems. Discrete Appl Math. 2017;219:83–99.
  • Merlet G, Nowak T, Sergeev S. Weak CSR expansions and transience bounds in max-plus algebra. Linear Algebra Appl. 2014;461:163–199.
  • Baccelli F, Hong D. TCP is max-plus linear and what it tells us on its throughput. Proceedings of the conference on applications, technologies, architectures, and protocols for computer communication (SIGCOMM 2000); New York (NY): ACM; 2000, p. 219–230.
  • Cohen G, Moller P, Quadrat J-P, et al. Algebraic tools for the performance evaluation of discrete event systems. Proc IEEE. 1989;77(1):39–85.
  • Charron-Bost B, Függer M, Welch JL, et al. Time complexity of link reversal routing. ACM Trans Alg. 2015;11(3):18–00.
  • Even S, Rajsbaum S. The use of a synchronizer yields the maximum computation rate in distributed networks. Theor Comput Syst. 1997;30:447–474.
  • Baccelli F, Cohen G, Olsder GJ, et al. Synchronization and linearity: an algebra for discrete event systems. Chichester: Wiley; 1992.
  • Brualdi RA, Ryser HJ. Combinatorial matrix theory. Cambridge: Cambridge University Press; 1991.
  • Wielandt H. Unzerlegbare, nicht negative Matrizen. Mathematische Zeitschrift. 1950;52(1):642–645.
  • Dulmage AL, Mendelsohn NS. Gaps in the exponent set of primitive matrices. Illinois J Math. 1964;8(4):642–656.
  • Merlet G, Nowak T, Sergeev S, et al. Generalizations of bounds on the index of convergence to weighted digraphs. Discrete Appl Math. 2014;178:121–134.
  • Sergeev S. Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes. Linear Algebra Appl. 2009;431(6):1325–1339.
  • Sergeev S, Schneider H. CSR expansions of matrix powers in max algebra. Trans AMS. 2012;364:5969–5994.
  • Shao J-y.. On the exponent of a primitive digraph. Linear Algebra Appl. 1985;64:21–31.
  • Schneider H, Schneider MH. Max-balancing weighted directed graphs and matrix scaling. Math Oper Res. 1991;16:208–222.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.