Powers of matrices over an extremal algebra with applications to periodic graphs

DOI10.1007/BF01199464zbMath0885.90111MaRDI QIDQ1366320

Karl Nachtigall

Publication date: 10 September 1997

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

zbMATH Keywords

1-dimensional periodic graphextremal algebraminimum cost path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Max algebraic powers of irreducible matrices in the periodic regime: an application of cyclic classes, On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product, Fiedler-Pták scaling in max algebra, Weak CSR expansions and transience bounds in max-plus algebra, Two cores of a nonnegative matrix, Unnamed Item, New bounds on the periodicity transient of the powers of a tropical matrix: using cyclicity and factor rank, Linear matrix period in max-plus algebra, Generalized matrix period in max-plus algebra, Generalizations of bounds on the index of convergence to weighted digraphs, Matrix Analysis and Omega Calculus, Computational Complexity of Nachtigall's Representation, Max-plus automata, CSR expansions of matrix powers in max algebra, Powers of matrices over distributive lattices -- a review, Unnamed Item, Key exchange protocol based upon a modified tropical structure

Cites Work

• Unnamed Item
• A characterization of the minimum cycle mean in a digraph
• Minimax algebra
• A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing
• On a new functional transform in analysis: The maximum transform
• Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
• Minimum Cost Paths in Periodic Graphs
• The Organization of Computations for Uniform Recurrence Equations