Publications [#236915] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH, A topological approach to dynamic graph connectivity, Information Processing Letters, vol. 25 no. 1 (April, 1987), pp. 65-70, Elsevier BV, ISSN 0020-0190 [pdf], [doi]
   (last updated on 2026/01/14)

   Abstract:
   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 Ω(n²). 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.