Abstract
Consider the extremal algebra
=(ℝ∪{∞},min,+), using + and min instead of addition and multiplication. This extremal algebra has been successfully applied to a lot of scheduling problems. In this paper the behavior of the powers of a matrix over
is studied. The main result is a representation of the complete sequence (A m) m∈ℕ which can be computed within polynomial time complexity. In the second part we apply this result to compute a minimum cost path in a 1-dimensional periodic graph.
Similar content being viewed by others
References
Bacceli F, Cohen G, Olsder G, Quadrat J (1992) Synchronization and linearity. J. Wiley and Sons
Backes W, Schwiegelshohn U, Thiele L (1992) Analysis of free schedule in period graphs. Proceedings of Symposium on Parallel Algorithms and Architectures: 333–343
Bellman R, Karush W (1961) A new functional transform in analysis: The maximum transform. Bull. Am. Math. Soc. 67:501–503
Carré B (1979) Graphs and networks. Oxford
Cohen E, Megiddo N (1993) Strongly polynomial-time and nc algorithms for detecting cycles in periodic graphs. Journal of the Association for Computing Machinery 40:791–830
Cohen G, Dubois D, Quadrat J, Viot M (1985) A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing. IEEE Transactions on Automatic Control, AC-30: 210–220
Cuninghame-Green R (1979) Minimax-algebra. Lecture Notes in economics and mathematical systems 166, Springer Verlag, Berlin, New York
Gondran M, Minoux M (1984) Graphs and algorithms. J. Wiley & Sons
Höfling F, Wanke E (1995) Polynomial algorithms for minimum cost paths in periodic graphs. SIAM Journal on Computing: 1051–1067
Iwano K, Steiglitz K (1987) Testing for cycles in infinite graphs with periodic structure. Proceedings of Annual ACM Symposium on Theory of Computing: 46–55
Karp R (1978) A characterization of the minimum cycle mean in a digraph. Discrete Mathematics 23:309–311
Karp R, Miller R, Winograd S (1967) The organization of computations for uniform recurrence equations. J. ACM 2:563–590
Orlin JB (1984) Some problems on dynamic/periodic graphs. In: Progress in Combinatorial Optimization: 273–293
Worobjov N (1967) Extremal algebra of positive matrices. (in Russian), Elektronische Informationsverarbeitung und Kybernetik
Zimmermann U (1981) Linear and combinatorial optimization in ordered algebraic structures. Annals of discrete mathematics 10, North Holland
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Nachtigall, K. Powers of matrices over an extremal algebra with applications to periodic graphs. Mathematical Methods of Operations Research 46, 87–102 (1997). https://doi.org/10.1007/BF01199464
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01199464