@article {IOPORT.06026921,
    author       = {Butkovi\v{c}, Peter},
    title        = {On the coefficients of the max-algebraic characteristic polynomial and equation.},
    year         = {2003},
    journal      = {Kybernetika},
    volume       = {39},
    number       = {2},
    issn         = {0023-5954},
    pages        = {129-136},
    publisher    = {Institute of Information Theory and Automation, Academy of Sciences of the Czech Republic, Prague},
    abstract     = {Summary: No polynomial algorithms are known for finding the coefficients of the characteristic polynomial and the characteristic equation of a matrix in max-algebra. The following statements are proved. (1) The task of finding the max-algebraic characteristic polynomial for permutation matrices encoded using the lengths of their constituent cycles is NP-complete. (2) The task of finding the lowest order finite term of the max-algebraic characteristic polynomial for a $\{0,-\infty \}$ matrix can be converted to the assignment problem. (3) The task of finding the max-algebraic characteristic equation of a $\{0,-\infty \}$ matrix can be converted to that of finding the conventional characteristic equation for a $\{0,1\}$ matrix, and thus it is solvable in polynomial time.},
    identifier   = {06026921},
}