The equation Ax=By over (max, +)

Raymond Cuninghame-Green, Peter Butkovic

Research output: Contribution to journalArticle

50 Citations (Scopus)

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 languageEnglish
Pages (from-to)3-12
Number of pages10
JournalTheoretical Computer Science
Volume293
Issue number1
DOIs
Publication statusPublished - 3 Feb 2003

Keywords

  • pseudopolynomial algorithm
  • linear system
  • max-algebra

Fingerprint

Dive into the research topics of 'The equation Ax=By over (max, +)'. Together they form a unique fingerprint.

Cite this