Incremental and Decremental Evaluation of Transitive Closure by First-Order Queries Title

Incremental and Decremental Evaluation of Transitive Closure by First-Order Queries

Guozhu Dong, The University of Melbourne

Jianwen Su, University of California, Santa Barbara

Status

in Information and Computation, pp. 101-106, 1:120, July 1995. Preliminary results presented at the 1993 Australian Computer Science Conference.

Abstract

We study the following problem. Suppose G is a graph and TCG its transitive closure. If G' is a new graph obtained from G by inserting or deleting an edge e, can the new transitive closure TCG' be defined in first-order logic using G, TCG and e? In this paper, we show that the answer is positive for (1) acyclic graphs (main result), (2) graphs where the vertices of the deleted edge are not in the same strongly-connected component, and (3) graphs where there exists at most one path between each pair of vertices (0-1-path graphs). It is left open whether the new transitive closure is definable in first-order logic for all graphs. We also consider the first-order on-line computation of the dominator relation.