Polynomial algorithm for linear matrix period in max-plus algebra
The author proves that if the matrix \(A\) is almost linear periodic, the linear factor matrix and the linear period of \(A\) can be computed in \(O(n^3)\) time. On the other hand, it is shown that the computation of the coordinate linear period \(I\text{ per}(a^*_{ij})\) for given indices, \(i,j\in n\) is an NP-hard problem. Further, a polynomial algorithm is described, which decides whether a given matrix \(A\) is almost linear periodic, if \(A\) fulfills the condition of incomparable trivial strongly connected components. The results of this paper may be useful in computing the linear period of periodic graphs, or in investigating the periodic behaviour and stability of discrete event system.
- Linear matrix period in max-plus algebra
- Generalized matrix period in max-plus algebra
- Computational complexity of periodicity problems in max-plus algebra
- scientific article; zbMATH DE number 1516306 (Why is no real title available?)
- On Eigenproblem for Circulant Matrices in Max-Algebra
- Computational Complexity of Nachtigall's Representation
- Computing periodic request functions to speed-up the analysis of non-cyclic task models
This page was built for publication: Polynomial algorithm for linear matrix period in max-plus algebra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5949928)
