A topological approach to dynamic graph connectivity

DOI10.1016/0020-0190(87)90095-0zbMath0653.68063OpenAlexW2083394054MaRDI QIDQ1108030

John H. Reif

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90095-0

zbMATH Keywords

planar graphdepth-first searchdynamic connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Related Items (13)

Complexity models for incremental computation ⋮ The incremental maintenance of a depth-first-search tree in directed acyclic graphs ⋮ The complexity of certain incremental code generation problems ⋮ On the computational complexity of dynamic graph problems ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ On Dynamic DFS Tree in Directed Graphs ⋮ Computing the well-founded semantics faster ⋮ Dynamic connectivity in disk graphs ⋮ Maintaining bridge-connected and biconnected components on-line ⋮ Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time ⋮ Unnamed Item ⋮ Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier

Uses Software

• Algorithm 447

Cites Work

• Depth-first search is inherently sequential
• An observation on time-storage trade off
• Complete problems for deterministic polynomial time
• An On-Line Edge-Deletion Problem
• Efficient Planarity Testing
• Efficiency of a Good But Not Linear Set Union Algorithm
• Dividing a Graph into Triconnected Components
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item

This page was built for publication: A topological approach to dynamic graph connectivity