|
Published Articles >> Table of Contents >> Abstract
10th International Symposium on Temporal Representation and Reasoning and Fourth International Conference on Temporal Logic
p. 212
A New Efficient Algorithm for Solving the Simple Temporal Problem
Lin Xu, University of Nebraska-Lincoln
Berthe Y. Choueiry, University of Nebraska-Lincoln
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TIME.2003.1214898
Send link to a friend
| Abstract |
|
In this paper we propose a new efficient algorithm, the \bigtriangleupSTP-solver, for computing the minimal network of the Simple Temporal Problem (STP). This algorithm achieves high performances by exploiting a topological property of the constraint graph (i.e., triangulation) and a semantic property of the constraints (i.e., convexity) in light of the results reported by Bliek and Sam-Haroud [1], which were presented for general CSPs and have not yet been applied to temporal networks. Importantly, we design the constraint propagation in \bigtriangleupSTP-solver to operate on triangles instead of operating on edges and implicitly guarantee the decomposition of the constraint graph according to its articulation points. We also provide extensive empirical evaluations of all known algorithms for solving the STP on sets of randomly generated problems. Our experiments demonstrate significant improvements of \bigtriangleupSTP- solver, in terms of number of constraint checks and CPU time, over previously reported algorithms such as the Floyd-Warshall algorithm (F-W) [5; 8], Directed-Path Consistency (DPC) [8], and Partial Path-Consistency (PPC) [1].
|
 Additional Information
|
Citation:
Lin Xu, Berthe Y. Choueiry,
"A New Efficient Algorithm for Solving the Simple Temporal Problem,"
time-ictl,
p. 212,
10th International Symposium on Temporal Representation and Reasoning and Fourth International Conference on Temporal Logic,
2003
|
|
