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.
Repository Citation
Dong, G.,
& Pang, C.
(1997). Maintaining Transitive Closure in First Order After Node-Set and Edge-Set Deletions. Information Processing Letters, 62 (4), 193-199.
https://corescholar.libraries.wright.edu/knoesis/300
DOI
10.1016/S0020-0190(97)00066-5
