Powers of matrices over an extremal algebra with applications to periodic graphs

Consider the extremal algebra[Figure not available: see fulltext.]=(ℝ∪{∞},min,+), using + and min instead of addition and multiplication. This extremal algebra has been successfully applied to a lot of scheduling problems. In this paper the behavior of the powers of a matrix over[Figure not available: see fulltext.] is studied. The main result is a representation of the complete sequence (A <Superscript> m </Superscript>)<Subscript> m∈ℕ</Subscript> which can be computed within polynomial time complexity. In the second part we apply this result to compute a minimum cost path in a 1-dimensional periodic graph. Copyright Physica-Verlag 1997