Finding all essential terms of a characteristic maxpolynomial

RE Burkard, Peter Butkovic

Research output: Contribution to journalArticle

17 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)367-380
Number of pages14
JournalDiscrete Applied Mathematics
Issue number3
Publication statusPublished - 23 Aug 2003


  • assignment problem
  • max-algebra
  • characteristic maxpolynomial


Dive into the research topics of 'Finding all essential terms of a characteristic maxpolynomial'. Together they form a unique fingerprint.

Cite this