Computing All-Pairs Shortest Paths by Leveraging Low Treewidth (extended abstract)

P³C: A New Algorithm for the Simple Temporal Problem

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...