Updating ⩽,<-chains

✍ Scribed by James P. Delgrande; Arvind Gupta

• Book ID: 104136688
• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 125 KB
• Volume: 82
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00278-2

✦ Synopsis

We address the problem of very efficient reasoning and update in , <-chains, where a , <-chain is a directed acyclic graph such that there is a directed path between every pair of vertices, and edges are consistently labeled by or <. It is easy to show that, subsequent to an O(n) labeling scheme, queries concerning implied and < relations can be answered in O(1) time. However this scheme does not allow for efficient updates to a chain. We show via a novel encoding of precedence information that updates to chains can be accomplished very efficiently. For edge or vertex addition, updates can be carried out in O(log n) time, with manageable degradation for queries: queries are answered in O(1) time while < queries require O(log n) time. This result is surprising, in that in the obvious approach to updates O(n) time is required.