Conditions for the structural existence of an eigenvalue of a bipartite (min,max,+)-system

✍ Scribed by Jacob van der Woude; Subiono

• Book ID: 104325438
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 148 KB
• Volume: 293
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00229-3

✦ Synopsis

In this paper we consider bipartite (min; max; +)-systems. We present conditions for the structural existence of an eigenvalue and corresponding eigenvector for such systems, where both the eigenvalue and eigenvector are supposed to be ÿnite. The conditions are stated in terms of the system matrices that describe a bipartite (min; max; +)-system. Structural in the previous means that not so much the numerical values of the ÿnite entries in the system matrices are important, rather than their locations within these matrices. The conditions presented in this paper can be seen as an extension towards bipartite (min; max; +)-systems of known conditions for the structural existence of an eigenvalue of a (max; +)-system involving the (ir)reducibility of the associated system matrix. Although developed for bipartite (min; max; +)-systems, the conditions for the structural existence of an eigenvalue also can directly be applied to general (min; max; +)-systems when given in the so-called conjunctive or disjunctive normal form.