Skip to main content
Journal cover image

A topological approach to dynamic graph connectivity

Publication ,  Journal Article
Reif, JH
Published in: Information Processing Letters
April 20, 1987

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

Published In

Information Processing Letters

DOI

ISSN

0020-0190

Publication Date

April 20, 1987

Volume

25

Issue

1

Start / End Page

65 / 70

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 40 Engineering
  • 09 Engineering
  • 08 Information and Computing Sciences
  • 01 Mathematical Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (1987). A topological approach to dynamic graph connectivity. Information Processing Letters, 25(1), 65–70. https://doi.org/10.1016/0020-0190(87)90095-0
Reif, J. H. “A topological approach to dynamic graph connectivity.” Information Processing Letters 25, no. 1 (April 20, 1987): 65–70. https://doi.org/10.1016/0020-0190(87)90095-0.
Reif JH. A topological approach to dynamic graph connectivity. Information Processing Letters. 1987 Apr 20;25(1):65–70.
Reif, J. H. “A topological approach to dynamic graph connectivity.” Information Processing Letters, vol. 25, no. 1, Apr. 1987, pp. 65–70. Scopus, doi:10.1016/0020-0190(87)90095-0.
Reif JH. A topological approach to dynamic graph connectivity. Information Processing Letters. 1987 Apr 20;25(1):65–70.
Journal cover image

Published In

Information Processing Letters

DOI

ISSN

0020-0190

Publication Date

April 20, 1987

Volume

25

Issue

1

Start / End Page

65 / 70

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 40 Engineering
  • 09 Engineering
  • 08 Information and Computing Sciences
  • 01 Mathematical Sciences