Computing matrix period in max-min algebra

被引：38
作者：
Gavalec, M
机构：
[1] Department of Mathematics, Fac. of Elec. Eng. and Informatics, Technical University, 04201 Kosice
来源：
DISCRETE APPLIED MATHEMATICS | 1997年 / 75卷 / 01期
关键词：
max-min matrix; period of a matrix; max-min algebra; threshold graph; strongly connected component of a digraph;
D O I：
10.1016/S0166-218X(96)00079-0
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Periodicity of matrix powers in max-min algebra is studied. The period of a matrix A is shown to be the least common multiple of the periods of at most n non-trivial strongly connected components in some threshold digraphs of A. An O(n(3)) algorithm for computing the period is described.
引用
收藏
页码：63 / 70
页数：8
相关论文
共 11 条
[1]   MODULARITY OF CYCLES AND PATHS IN GRAPHS [J].
ARKIN, EM ;
PAPADIMITRIOU, CH ;
YANNAKAKIS, M .
JOURNAL OF THE ACM, 1991, 38 (02) :255-274
[2]  
BALCER Y, 1973, DISCRETE MATH, V38, P295
[3]   EIGENVECTORS IN BOTTLENECK ALGEBRA [J].
CECHLAROVA, K .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1992, 175 :63-73
[4]  
CECHLAROVA K, 2193 U BIRM
[5]  
Cuninghame-Green RA., 1979, Minimax Algebra
[6]  
GONDRAN M, 1978, C INT CNRS PAR, P181
[7]  
LI JX, 1992, FUZZY SET SYST, V48, P365, DOI 10.1016/0165-0114(92)90351-4
[8]  
LI JX, 1992, FUZZY SET SYST, V49, P317, DOI 10.1016/0165-0114(92)90283-A
[9]   CONVERGENCE OF POWERS OF A FUZZY MATRIX [J].
THOMASON, MG .
JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1977, 57 (02) :476-480
[10]   A THEOREM ON BOOLEAN MATRICES [J].
WARSHALL, S .
JOURNAL OF THE ACM, 1962, 9 (01) :11-&
12