A topological approach to dynamic graph connectivity


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • April 20, 1987

Published In

Volume / Issue

  • 25 / 1

Start / End Page

  • 65 - 70

International Standard Serial Number (ISSN)

  • 0020-0190

Digital Object Identifier (DOI)

  • 10.1016/0020-0190(87)90095-0

Citation Source

  • Scopus