Alfonso Gerevini and Lenhart Schubert, "An efficient method for managing disjunctions in qualitative temporal reasoning", In: Principles of Knowledge Representation and Reasoning: Proceedings of the Fourth International Conference (KR94), Morgan Kaufmann, San Mateo, CA, 1994.
Alfonso Gerevini and Lenhart Schubert, Efficient algorithms for qualitative reasoning about time, University of Rochester, Computer Science Department, Technical Report 496, March 1994.
In traditional temporal reasoning formalisms of Artificial Intelligence (AI), the knowledge about events is described by relations between time intervals during which these events occur. After we get all the information from the experts, we must also add consequences of these relations; in AI, this procedure is called a {\it closure}. For $n$ events, computing the closure takes time $O(n^4)$. From the viewpoint of theoretical computer science, this is polynomial time and thus, the closure algorithm is {\it feasible}. In reality, for large $n$, this time is too long.
To decrease the time necessary for computing a closure, the authors take into consideration the fact that usually, in large knowledge bases, events can be subdivided into chains with practically no interactions between the chains. Thus, if we describe the events as a graph, this graph can be reduced to several barely connected subgraphs. and this structuredness drastically decreases the required computation time.