An Efficient Algorithm for the Maximum Distance Problem

Abstract : Efficient algorithms for temporal reasoning are essential in knowledge-based systems. This is central in many areas of Artificial Intelligence including scheduling, planning, plan recognition, and natural language understanding. As such, scalability is a crucial consideration in temporal reasoning. While reasoning in the interval algebra is NP-complete, reasoning in the less expressive point algebra is tractable. In this paper, we explore an extension to the work of Gerevini and Schubert which is based on the point algebra. In their seminal framework, temporal relations are expressed as a directed acyclic graph partitioned into chains and supported by a \emphmetagraph data structure, where time points or events are represented by vertices, and directed edges are labelled with < or ≤ . They are interested in fast algorithms for determining the strongest relation between two events. They begin by developing fast algorithms for the case where all points lie on a chain. In this paper, we are interested in a generalization of this, namely we consider the problem of finding the maximum ''distance'' between two vertices in a \emphchain; this problem arises in real world applications such as in process control and crew scheduling. We describe an O(n) time preprocessing algorithm for the maximum distance problem on chains. It allows queries for the maximum number of < edges between two vertices to be answered in O(1) time. This matches the performance of the algorithm of Gerevini and Schubert for determining the strongest relation holding between two vertices in a chain.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.323-350
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958965
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:53:49
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:05:34

Fichier

dm040218.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958965, version 1

Collections

Citation

Gabrielle Assunta Grün. An Efficient Algorithm for the Maximum Distance Problem. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2001, 4 (2), pp.323-350. 〈hal-00958965〉

Partager

Métriques

Consultations de la notice

117

Téléchargements de fichiers

308