Finding all essential terms of a characteristic maxpolynomial

Let us denote a circle plus b = max(a,b) and a circle times b =a + b for a, b is an element of (R) over bar = R boolean OR {-infinity} and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n(2)(m + n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n x n matrix over (R) over bar with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n x 11 matrix A and kis an element of {1,...n} find a k x k principal submatrix of A whose assignment problem value is maximum. (C) 2003 Elsevier B.V. All rights reserved.