P<sup>3</sup> C

A new algorithm for the Simple Temporal Problem

Conference paper (2008)

Authors

L.R. Planken Algorithmics -

M.M. de Weerdt Algorithmics -

R.P.J. van der Krogt Cork Constraint Computation Centre

Research Group

Algorithmics () (TU Delft)

More Info

expand_more

To reference this document use:

http://resolver.tudelft.nl/uuid:9f20a10c-3a6e-4823-bd60-757cc041a7fc

Published Date

01-12-2008

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Technology

Research Group

Algorithmics

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.