A strongly polynomial algorithm for solving two-sided linear systems in max-algebra |
| |
| Authors: | Peter Butkovi? Karel Zimmermann |
| |
| Institution: | a School of Mathematics, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK
b Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic |
| |
| Abstract: | An algorithm for solving m×n systems of (max,+)-linear equations is presented. The systems have variables on both sides of the equations. After O(m4n4) iterations the algorithm either finds a solution of the system or finds out that no solution exists. Each iteration needs O(mn) operations so that the complexity of the presented algorithm is O(m5n5). |
| |
| Keywords: | Max-algebra Two-sided equation Strongly polynomial algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
