Characterization of the Eigenvalue of a General Irreducible (Min, Max,+)-System.

摘要

In this paper we consider general (min, max, +)-systems and we introduce a kind of irreducibility for such systems. We show that the introduced notion of irreducibility is equivalent to the structural existence of the eigenvalue and a corresponding eigenvector, where we assume both the eigenvalue and the eigenvector to be finite. Structural existence in the previous means that the existence does not so much depend on the numerical values of the coefficients in the equations describing the system, rather than on their locations within these equations. The major contribution of this paper is an alternative characterization of the eigenvalue of a (min, max, +)-system that is irreducible in the above sense. We illustrate the results for (min, max, +)-systems by considering the consequences for two well-known subclasses, namely irreducible (max, +)-systems and irreducible bipartite (min, max, +)-systems. Also we show how the obtained alternative characterization gives rise to a new conceptual algorithm to compute the eigenvalue of a (min, max, +)-system that is irreducible in the above sense.