A topological approach to dynamic graph connectivity

A dynamic connectivity problem consists of an initial graph, and a sequence of operations consisting of graph modifications and graph connectivity tests. The size n of the problem is the sum of the maximum number of vertices and edges of the derived graph, plus the number of operations to be executed. Each graph modification is a deletion of either an edge or an isolated vertex. Each graph connectivity test is to determine if there exists a path in the current graph between two given vertices (the vertices can vary for distinct tests). The best previously known time for this dynamic connectivity problem was Ω(n2). Our main result is an O(ng+n log n) time algorithm for the dynamic connectivity problem in the case of the maximum genus of the derived graph being g. © 1987.

Duke Scholars

Author John H. Reif Computer Science