On‐line connectivity algorithms
Grant A. Cheston · Networks · 1984
Abstract The problem is to be able to respond to inquiries of the form “Are vertices u and v of graph G connected?” as quickly as possible in an on‐line situation where edges are being inserted into and deleted from the graph. Recently Even and Shiloach presented a data structure and algorithm involving three synchronized processes to handle the deletion case. An alternative algorithm, LEVELS, is presented to update their data structure. This algorithm is more efficient than theirs and has the further feature of not requiring synchronized processes, so that it is much easier to implement. Finally the LEVELS algorithm is compared to and contrasted with an algorithm using a spanning‐forest data structure for both edge insertion and deletion. The LEVELS algorithm appears to be better for deletion, while the spanning‐forest algorithm is better for insertion.