Computational Complexity of Nachtigall's Representation
Monika Molnárová · Optimization · 2003
The matrix power sequences in max-plus algebra are studied. The power sequence of a given matrix can be represented by at most n almost linear periodic sequences as described by Nachtigall (1997), 'Powers of matrices over an extremal algebra with applications to periodic graphs' ( Math. Methods of Oper. Research , 46 , 87-102). A more efficient algorithm for finding such a representation in more general structure is described. The improved computational complexity is shown to be O ( n 5 ).