The semiring \((\overline R,\oplus,\otimes)\) is called max-plus algebra, where \(\overline R\) denotes the reals extended by \(-\infty\), where \(\oplus\) is the maximum operator, and \(\otimes\) the common product in \(\overline R\) with \(-\infty\) as null-element. Then, matrices and interval matrices are defined over \(\overline R\). They can be used to model the behaviour of discrete-event systems. A vector \(x\in\overline R^n\) is called a possible eigenvector of an interval matrix \(A^I= [\underline A, \overline A]\) if there exists a matrix \(A\in A^I\) such that \(x\) is an eigenvector of \(A\) (with respect to the semiring operations). The vector \(x\) is called a universal eigenvector of \(A^I\) if \(x\) is an eigenvector of each \(A\in A^I\). It is further assumed that the left endpoint matrix \(\underline A\) of \(A^I\) is irreducible. Then each \(A\in A^I\) has exactly one eigenvector. The paper shows that the problem to decide whether a given vector \(x\in\overline R^n\) is a possible eigenvector is polynomial. The complexity of the problem to decide whether \(A^I\) has a universal eigenvector is still open. Besides, a combinatorial method for solving two-sided systems of linear equations over \(\overline R\) is developed.