Linear matrix period in max-plus algebra

被引：24

作者：

Gavalec, M ^{[1
]}

机构：

[1] Tech Univ Kosice, Fac EE & Informat, Dept Math, Kosice 04200, Slovakia

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2000年 / 307卷 / 1-3期

关键词：

linear matrix period; max-plus algebra; NP-completeness;

D O I：

10.1016/S0024-3795(00)00020-3

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Linear periodicity of matrices in max-plus algebra is studied. It is proved that the linear period of a matrix can be computed in O(n(3)) time if the digraph of the matrix is strongly connected. The general problem of deciding whether a given matrix is almost linear periodic is shown to be NP-complete. (C) 2000 Published by Elsevier Science Inc. All rights reserved.

引用

页码：167 / 182

页数：16

共 18 条

[1]

BACCELI F, 1992, SYNCHRONIZATION LIEN

[2]

BALCER Y, 1973, DISCRETE MATH, V38, P295

[3] On the powers of matrices in bottleneck/fuzzy algebra [J].

Cechlarova, K .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1996, 246 :97-111

[4] A LINEAR-SYSTEM-THEORETIC VIEW OF DISCRETE-EVENT PROCESSES AND ITS USE FOR PERFORMANCE EVALUATION IN MANUFACTURING [J].

COHEN, G ;

DUBOIS, D ;

QUADRAT, JP ;

VIOT, M .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1985, 30 (03) :210-220

[5]

Cuninghame-Green RA., 1979, Minimax Algebra

[6]

DRAZENSKA E, 1998, P C INF ALG PRES, P327

[7]

Gavalec M., 1997, Tatra Mountains Mathematical Publications, V12, P81

[8] Computing matrix period in max-min algebra [J].

Gavalec, M .

DISCRETE APPLIED MATHEMATICS, 1997, 75 (01) :63-70

[9] Computing orbit period in max-min algebra [J].

Gavalec, M .

DISCRETE APPLIED MATHEMATICS, 2000, 100 (1-2) :49-65

[10]

GAVALEC M, UNPUB CTR EUR J OPER

← 1 2 →