Abstract
For the two-sided homogeneous linear equation system A circle times x = B circle times y over (max, +), with no infinite rows or columns in A or B, an algorithm is presented which converges to a finite solution from any finite starting point whenever a finite solution exists. If the finite elements of A, B are all integers, convergence is in a finite number of steps, for which a precise bound can be calculated if moreover one of A, B has only finite elements. The algorithm is thus pseudopolynomial in complexity. (C) 2002 Elsevier Science B.V. All rights reserved.
Original language | English |
---|---|
Pages (from-to) | 3-12 |
Number of pages | 10 |
Journal | Theoretical Computer Science |
Volume | 293 |
Issue number | 1 |
DOIs | |
Publication status | Published - 3 Feb 2003 |
Keywords
- pseudopolynomial algorithm
- linear system
- max-algebra