# Discrete Mathematics & Theoretical Computer Science

## Volume 4 n° 2 (2001), pp. 323-350

author: | Gabrielle Assunta Grün |
---|---|

title: | An Efficient Algorithm for the Maximum Distance Problem |

keywords: | graph theory,analysis of algorithms and data structures, maximum distance problem, temporal reasoning |

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
metagraph 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 chain; 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. |

reference: | Gabrielle Assunta Grün (2001),
An Efficient Algorithm for the Maximum Distance Problem,
Discrete Mathematics and Theoretical Computer Science 4, pp. 323-350 |

bibtex: | For a corresponding BibTeX entry, please consider our BibTeX-file. |

ps.gz-source: | dm040218.ps.gz (188 K) |

ps-source: | dm040218.ps (569 K) |

pdf-source: | dm040218.pdf (366 K) |

The first *source* gives you the `gzipped' PostScript, the second the plain
PostScript and the third the format for the Adobe accrobat
reader. Depending on the installation of your web browser, at least
one of these should (after some amount of time) pop up a window for
you that shows the full article. If this is not the case, you should
contact your system administrator to install your browser correctly.

Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.

Automatically produced on Tue Dec 11 22:57:32 CET 2001 by ifalk