×

zbMATH — the first resource for mathematics

Computing matrix period in max–min algebra. (English) Zbl 0876.05070
Summary: Periodicity of matrix powers in max–min algebra is studied. The period of a matrix \(A\) is shown to be the least common multiple of the periods of at most \(n\) nontrivial strongly connected components in some threshold digraphs of \(A\). An \(O(n^3)\) algorithm for computing the period is described.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Arkin, E.M.; Papadimitriou, C.H.; Yannakakis, M., Modularity of cycles and paths in graphs, J. ACM, 38, 255-274, (1991) · Zbl 0799.68146
[2] Balcer, Y.; Veinott, A.F., Computing a Graph’s period quadratically by node condensation, Discrete math., 38, 295-303, (1973) · Zbl 0258.05114
[3] K. Cechlárová, On the powers of matrices in bottleneck/fuzzy algebra, preprint 21/93, University of Birmingham.
[4] Cechlárová, K., Eigenvectors in bottleneck algebra, Linear algebra appl., 175, 63-73, (1992) · Zbl 0756.15014
[5] Cuninghame-green, R.A., Minimax algebra, () · Zbl 0498.90084
[6] Gondran, M.; Minoux, M., Valeurs propres et vecteurs propres en théorie des graphes, (), 181-183 · Zbl 0414.15011
[7] Li, Jian-xin, Periodicity of powers of fuzzy matrices (finite fuzzy relations), Fuzzy sets and systems, 48, 365-369, (1992) · Zbl 0760.15012
[8] Li, Jian-xin, An upper bound on indices of finite fuzzy relations, Fuzzy sets and systems, 49, 317-321, (1992) · Zbl 0782.04010
[9] Thomason, M.G., Convergence of powers of a fuzzy matrix, J. math. anal. appl., 57, 476-480, (1977) · Zbl 0345.15007
[10] Warshall, D., A theorem on Boolean matrices, J. ACM, 9, 11-12, (1962) · Zbl 0118.33104
[11] Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, () · 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. 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.