A topological approach to dynamic graph connectivity
From MaRDI portal
Publication:1108030
DOI10.1016/0020-0190(87)90095-0zbMath0653.68063MaRDI QIDQ1108030
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
68Q25: Analysis of algorithms and problem complexity
68P10: Searching and sorting
68R10: Graph theory (including graph drawing) in computer science
05C40: Connectivity
Related Items
The complexity of certain incremental code generation problems, Maintaining bridge-connected and biconnected components on-line, Complexity models for incremental computation, On the computational complexity of dynamic graph problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- 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