Efficient Algorithms for Networks of Quantitative Temporal Constraints

This paper describes two algorithms for networks of quantitative temporal constraints. The ørst one is an incremental algorithm for checking the consistency of a set of constraints: it is based on the directional path consistency property, and it is a complete algorithm. The second algorithm relies on a property of shortest paths in a directional path consistent network. We prove this property and present an efficient linear-time algorithm that has a lower cost than usual shortest-path algorithm such as BellmanFord algorithm. These two algorithms form a complete system for managing quantitative temporal relationships