P3 C
A new algorithm for the Simple Temporal Problem
Léon Planken (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Mathijs De Weerdt (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Roman Van Der Krogt (Cork Constraint Computation Centre)
More Info
expand_more
Abstract
The Simple Temporal Problem (STP) is a sub-problem of almost any planning or scheduling problem involving time constraints. An existing efficient method to solve the STP, called ΔSTP, 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, P3C, whose worst-case time complexity is linear in the number of triangles. We show both formally and experimentally that P3C outperforms ΔSTP significantly.
No files available
Metadata only record. There are no files for this record.