Computing orbit period in max-min algebra

被引：21
作者：
Gavalec, M [1 ]
机构：
[1] Tech Univ, Fac Elect Engn & Informat, Dept Math, Kosice 04213, Slovakia
来源：
DISCRETE APPLIED MATHEMATICS | 2000年 / 100卷 / 1-2期
关键词：
period of a matrix; orbit of a vector; max-min algebra; NP-completeness;
D O I：
10.1016/S0166-218X(99)00174-2
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Periodicity of vector orbits in max-min algebra is studied. It is proved that computing the coordinate-orbit period is NP-hard, while the orbit period can be computed in O(n(4)) time. A related problem of maximum sequence period is shown to be NP-complete. (C) 2000 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：49 / 65
页数：17
相关论文
共 13 条
  • [1] BALCER Y, 1973, DISCRETE MATH, V38, P295
  • [2] On the powers of matrices in bottleneck/fuzzy algebra
    Cechlarova, K
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 1996, 246 : 97 - 111
  • [3] Cuninghame-Green RA., 1979, Minimax Algebra
  • [4] DRAZENSKA E, 1998, P C INF ALG PRES, P327
  • [5] Gavalec M., 1997, Tatra Mountains Mathematical Publications, V12, P81
  • [6] Computing matrix period in max-min algebra
    Gavalec, M
    [J]. DISCRETE APPLIED MATHEMATICS, 1997, 75 (01) : 63 - 70
  • [7] THE PROBLEM OF COMPATIBLE REPRESENTATIVES
    KNUTH, DE
    RAGHUNATHAN, A
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (03) : 422 - 427
  • [8] LI JX, 1992, FUZZY SET SYST, V48, P365, DOI 10.1016/0165-0114(92)90351-4
  • [9] LI JX, 1992, FUZZY SET SYST, V49, P317, DOI 10.1016/0165-0114(92)90283-A
  • [10] Molnarova M., 1999, Tatra Mountains Mathematical Publications, V16, P135
12