Paul G. Comba
Journal of the ACM
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. © 1981, ACM. All rights reserved.
Paul G. Comba
Journal of the ACM
Hagen Soltau, Lidia Mangu, et al.
ASRU 2011
S. Winograd
Journal of the ACM
P. Trespeuch, Y. Fournier, et al.
Civil-Comp Proceedings