An On-Line Edge-Deletion Problem

Abstract

There is given an undirected graph G -- (V, E) from which edges are deleted one at a time and about which questions of the type, "Are the vertices u and v in the same connected component?" have to be answered "on-line." There is presented an algorithm which maintains a data structure in which each question is answered in constant time and for which the total time involved in answering q questions and maintaining the data structure is O(q + I VI" lED.