Plávka, Ján On eigenproblem for circulant matrices in max-algebra. (English) Zbl 1005.90054 Optimization 50, No. 5-6, 477-483 (2001). Summary: The eigenproblem for circulant matrices in max-algebra is shown to be solvable in \(O(n^2)\) time. An algorithm is described which for a given \(n\times n\) real circulant matrix \((a_{ij})\) computes an eigenvalue \(\lambda\) and all eigenvectors \(x= (x_1,\dots, x_n)\) such that \[ \max_{j=1,\dots, n} (a_{ij}+ x_j)= \lambda+ x_i,\quad i= 1,\dots, n. \] The results improve the standard \(O(n^3)\) algorithm used in the general case. Cited in 1 ReviewCited in 7 Documents MSC: 90C27 Combinatorial optimization 05B35 Combinatorial aspects of matroids and geometric lattices Keywords:eigenproblem; circulant matrix PDFBibTeX XMLCite \textit{J. Plávka}, Optimization 50, No. 5--6, 477--483 (2001; Zbl 1005.90054) Full Text: DOI References: [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, R.A. 1979. ”Minimax Algebra Lecture, Notes in Econ. and Math. Systems 166”. Berlin: Springer-Verlag. · Zbl 0399.90052 [4] Dantzig G.B., Theory of graphs (1967) · Zbl 0178.22701 [5] DOI: 10.1007/BF01386390 · Zbl 0092.16002 · doi:10.1007/BF01386390 [6] DOI: 10.1287/opre.25.5.741 · Zbl 0387.90080 · doi:10.1287/opre.25.5.741 [7] Gavalec M., Eigenproblem for Monge Matrices in max-Algebra · Zbl 0984.65042 [8] DOI: 10.1007/BF01399312 · Zbl 0541.65009 · doi:10.1007/BF01399312 [9] Karp R.M., Discrete Math 23 pp 309– (1978) [10] Lawler E.L., Combinatorial Optimization: Networks and Matroids Holt (1976) · Zbl 0413.90040 [11] DOI: 10.1080/02331939408843990 · Zbl 0815.68080 · doi:10.1080/02331939408843990 [12] DOI: 10.1137/0201010 · Zbl 0251.05107 · doi:10.1137/0201010 [13] Vorobyev N.N., Elektron. Informationsverarbeitung und Kybernetik 3 pp 39– (1967) [14] Zimmermann U., Linear and Combinatorial Optimization in Ordered .Algebraic Structures (1981) · Zbl 0466.90045 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.