A topological approach to dynamic graph connectivity
From MaRDI portal
Publication:1108030
DOI10.1016/0020-0190(87)90095-0zbMATH Open0653.68063OpenAlexW2083394054MaRDI QIDQ1108030FDOQ1108030
Authors: J. 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
Recommendations
- Near-optimal fully-dynamic graph connectivity
- A study of connectivity on dynamic graphs: computing persistent connected components
- A dynamical core for topological directed graphs
- Dynamic Subgraph Connectivity with Geometric Applications
- scientific article; zbMATH DE number 1256640
- Fully dynamic biconnectivity in graphs
- On some properties of dynamic graphs
- Connected dominating sets on dynamic geometric graphs
- scientific article; zbMATH DE number 2079390
- scientific article; zbMATH DE number 1496421
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Connectivity (05C40)
Cites Work
- Depth-First Search and Linear Graph Algorithms
- Efficient Planarity Testing
- Efficiency of a Good But Not Linear Set Union Algorithm
- An observation on time-storage trade off
- Depth-first search is inherently sequential
- Complete problems for deterministic polynomial time
- An On-Line Edge-Deletion Problem
- Dividing a Graph into Triconnected Components
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (21)
- Title not available (Why is that?)
- Complexity models for incremental computation
- On the computational complexity of dynamic graph problems
- Dynamic connectivity in disk graphs
- Connected dominating sets on dynamic geometric graphs
- Dynamic connectivity for axis-parallel rectangles
- Title not available (Why is that?)
- Efficiently testing \(T\)-interval connectivity in dynamic graphs
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Title not available (Why is that?)
- The incremental maintenance of a depth-first-search tree in directed acyclic graphs
- Maintaining bridge-connected and biconnected components on-line
- Dynamic connectivity in digital images
- A fast algorithm for connectivity graph approximation using modified Manhattan distance in dynamic networks
- Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
- Incremental algorithm for maintaining a DFS tree for undirected graphs
- Computing the well-founded semantics faster
- Maintaining regular properties dynamically in \(k\)-terminal graphs
- On Dynamic DFS Tree in Directed Graphs
- The complexity of certain incremental code generation problems
- Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
Uses Software
This page was built for publication: A topological approach to dynamic graph connectivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108030)
