ON COMPUTING THE MINIMAL LABELS IN TIME POINT ALGEBRA NETWORKS
Alfonso Gerevini, Lenhart K. Schubert · Computational Intelligence · 1995
We analyze the problem of computing the minimal labels for a network of temporal relations in point algebra. Van Beek proposes an algorithm for accomplishing this task, which takes O(max(n3, n2 m)) time (for n points and m ≠‐relations). We show that the proof of the correctness of this algorithm given by van Beek and Cohen is faulty, and we provide a new proof showing that the algorithm is indeed correct.