Powers of matrices over an extremal algebra with applications to periodic graphs
Powers of matrices over an extremal algebra with applications to periodic graphs
复制标题
极值代数矩阵的幂及其在周期图上的应用
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
K. Nachtigall
中科院分区：
文献类型：
--
作者：
K. Nachtigall
考虑极值代数=(ℝ∪{∞}，MIN，+)，用+和MIN代替加法和乘法。这种极值代数已经成功地应用于许多排序问题。本文研究了上矩阵的幂的性质。主要结果是可以在多项式时间复杂性内计算的完整序列(Am)m∈ℕ的表示。在第二部分中，我们将这一结果应用于一维周期图中的最小代价路径的计算。
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 (Am)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.