TY - GEN
T1 - P3 C
T2 - 18th International Conference on Automated Planning and Scheduling, ICAPS 2008
AU - Planken, Léon
AU - De Weerdt, Mathijs
AU - Van Der Krogt, Roman
PY - 2008/12/1
Y1 - 2008/12/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=58849101372&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:58849101372
SN - 9781577353867
T3 - ICAPS 2008 - Proceedings of the 18th International Conference on Automated Planning and Scheduling
SP - 256
EP - 263
BT - ICAPS 2008 - Proceedings of the 18th International Conference on Automated Planning and Scheduling
Y2 - 14 September 2008 through 18 September 2008
ER -