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

Document Type

Article

Publication Date

7-1995

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.

Copyright © 1995 Academic Press. All rights reserved.

DOI

10.1006/inco.1995.1102

Find in your library

Off-Campus WSU Users


Share

COinS