Polynomial algorithm for linear matrix period in max-plus algebra

Polynomial algorithm for linear matrix period in max-plus algebra

0.00 Avg rating0 Votes
Article ID: iaor20012924
Country: Germany
Volume: 8
Issue: 3
Start Page Number: 247
End Page Number: 258
Publication Date: Jun 2000
Journal: Central European Journal of Operations Research
Authors:
Abstract:

Linear periodicity of matrices in max-plus algebra is studied. It is proved that the linear factor matrix and the linear period of a matrix A can be computed in O(n3) time, if A is almost linear periodic. Computation of the coordinate linear period lper (a*ij) for given indices i,jn is shown to be NP-hard. Further, a polynomial algorithm is described, which decides whether a given matrix is almost linear periodic, if the matrix fulfils a condition of incomparability for trivial strongly connected components. In general, this problem is NP-complete.

Reviews

Required fields are marked *. Your email address will not be published.