P 3 C: a new algorithm for the simple temporal problem
Léon Planken, Mathijs M. De Weerdt, Roman van der Krogt · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 2008
The Simple Temporal Problem (STP) is a sub-problem of almost any planning or scheduling problem involving time constraints.An efficient method to solve the STP, called STP (Xu and Choueiry 2003), is based on partial path consistency and starts from a chordal constraint graph.In this paper, we analyse this algorithm and show that there exist instances for which its time complexity is quadratic in the number of triangles in the constraint graph.We propose a new algorithm, P 3 C, whose worst-case time complexity is linear in the number of triangles.We show both formally and experimentally that P 3 C outperforms STP significantly.* Application of the architecture sketched here is not limited to scheduling over time; Srivastava, Kambhampati, and Do (2001) propose a similar architecture to schedule over the available resources.* The term "triangulated graph" is also used for maximal planar graphs, which do not concern us here.