zbMATH — the first resource for mathematics

Eigenproblem for monotone and Toeplitz matrices in a max-algebra. (English) Zbl 1079.93033
Summary: The eigenproblem for monotone and Toeplitz matrices in a max-algebra is shown to be solvable in \(O(n^2)\) time. Two algorithms are described which, for a given \(n \times n\) real monotone and for a given \(n\times n\) real Toeplitz matrix compute an eigenvalue \({\lambda}\); and all eigenvectors of the form \(x = (x_1, x_2, \dots , x_n)\) such that
\[ \max (a_{ij} + x_j) = \lambda + x_i \text{ for \;all } i = 1,2,\dots,n. \]
These results improve standard \(O(n^3)\) algorithms used in the general case.

93C65 Discrete event control/observation systems
05B35 Combinatorial aspects of matroids and geometric lattices
90C27 Combinatorial optimization
Full Text: DOI
[1] DOI: 10.1016/0166-218X(92)90039-D · Zbl 0776.05070 · doi:10.1016/0166-218X(92)90039-D
[2] DOI: 10.1057/jors.1962.10 · doi:10.1057/jors.1962.10
[3] Cuninghame-Green RA, Minimax Algebra (1979)
[4] Dantzig GB, Theory of Graphs, Gordon and Breach (1967)
[5] DOI: 10.1007/BF01386390 · Zbl 0092.16002 · doi:10.1007/BF01386390
[6] DOI: 10.1016/S0166-218X(02)00395-5 · Zbl 1041.90045 · doi:10.1016/S0166-218X(02)00395-5
[7] Karp RM, Discrete Math 23 pp 309– (1978)
[8] Lawler EL, Combinatorial Optimization: Networks and Matriods, Holt, Rinehart and Wilston (1976)
[9] DOI: 10.1080/02331930108844576 · Zbl 1005.90054 · doi:10.1080/02331930108844576
[10] Vorobyev NN, Elektron. Informationsverarbeitung und Kybernetic 3 pp 39– (1967)
[11] Zimmermann U, Ann. Discrete Math. (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.