✦ LIBER ✦

An efficient algorithm for critical circuits and finite eigenvectors in the max-plus algebra

✍ Scribed by Geert-Jan Olsder; Kees Roos; Robert-Jan van Egmond

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 97 KB
Volume: 295
Category: Article
ISSN: 0024-3795
DOI: 10.1016/s0024-3795(99)00120-2

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the eigenvalue problem in the max-plus algebra for matrices in fÀI Rg nÂn but with eigenvectors in R n . The problem is relaxed to a linear optimization (LO) problem of which the dual problem is solved by ®nding a maximal average weight circuit in the graph of the matrix. The Floyd±Warshall procedure is used to ®nd such a circuit. This procedure also provides an ecient algorithm for ®nding an eigenvector.