Deciding consistency of a point-duration network with metric constraints
Isabel Navarrete, Abdul Rahman Sattar, R. Marı́n · 2004
We introduce a new model, MPDN, for quantitative temporal reasoning with points and durations, that supposes an extension of the TCSP formalism and previous point-duration network models. The problem of deciding consistency for a MPDN is shown to be NP-complete. So, we identify a tractable fragment, named simple MPDN, that subsumes the STP model and allows for duration reasoning. Necessary and sufficient conditions for deciding consistency of a simple MPDN are used to design an algorithm for consistency checking, whose time complexity is cubic in the number of variables. This is a significant improvement, not only in computational complexity but also in simplicity, over previous non-specific algorithms that can be applied to solve the consistency problem.