Title

Maintaining Transitive Closure in First Order After Node-Set and Edge-Set Deletions

Document Type

Article

Publication Date

5-27-1997

Abstract

We consider the problem of maintaining, using first-order formulas but without auxiliary relations, the transitive closure of directed graphs after the deletion of sets of edges and nodes; earlier results focused on edge-set insertions and single edge deletions. We give a generic result which asserts maintainability after deleting any “antichain” of edges. Many maintainability results follow, including after deleting any edge from acyclic graphs, after deleting any subset of all incoming (outgoing) edges to (from) any antichain family of strongly connected components (SCC), and after deleting any antichain of nodes. We then show maintainability after deleting all edges (or nodes) in any antichain family of SCCs. Finally, we show that maintainability after node deletions is at least as hard as after edge deletions.

DOI

10.1016/S0020-0190(97)00066-5

Find in your library

Off-Campus WSU Users


Share

COinS