The equation A⊗x=B⊗y over (max, +)

被引：61

作者：

Cuninghame-Green, RA ^{[1
]}

Butkovic, P ^{[1
]}

机构：

[1] Univ Birmingham, Sch Math & Stat, Birmingham B15 2TT, W Midlands, England

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 293卷 / 01期

关键词：

max-algebra; linear system; pseudopolynomial algorithm;

D O I：

10.1016/S0304-3975(02)00228-1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：3 / 12

页数：10