Polynomial precise interval analysis revisited

T Gawlitza, J Leroux, J Reineke, H Seidl… - … : Essays Dedicated to …, 2009 - Springer
Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His …, 2009Springer
We consider a class of arithmetic equations over the complete lattice of integers (extended
with-∞ and∞) and provide a polynomial time algorithm for computing least solutions. For
systems of equations with addition and least upper bounds, this algorithm is a smooth
generalization of the Bellman-Ford algorithm for computing the single source shortest path
in presence of positive and negative edge weights. The method then is extended to deal
with more general forms of operations as well as minima with constants. For the latter, a …
Abstract
We consider a class of arithmetic equations over the complete lattice of integers (extended with -∞ and ∞) and provide a polynomial time algorithm for computing least solutions. For systems of equations with addition and least upper bounds, this algorithm is a smooth generalization of the Bellman-Ford algorithm for computing the single source shortest path in presence of positive and negative edge weights. The method then is extended to deal with more general forms of operations as well as minima with constants. For the latter, a controlled widening is applied at loops where unbounded increase occurs. We apply this algorithm to construct a cubic time algorithm for the class of interval equations using least upper bounds, addition, intersection with constant intervals as well as multiplication.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果