An On-Line Edge-Deletion Problem
- 1 January 1981
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 28 (1) , 1-4
- https://doi.org/10.1145/322234.322235
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.Keywords
This publication has 1 reference indexed in Scilit:
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975