Dynamic connectivity: connecting to networks and geometry
From MaRDI portal
Abstract: Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental problems. Subgraph connectivity asks to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by "on" vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in O (m^{2/3}) amortized time, where m denotes the number of edges in the graph. This greatly improves over the previous result [Chan, STOC'02], which required fast matrix multiplication and had an update time of O(m^0.94). The new data structure is also simpler. Geometric connectivity asks to maintain a dynamic set of n geometric objects, and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously, nontrivial fully dynamic results were known only for special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, O (n^{2/3}), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear-time range queries, such as arbitrary 2D line segments, d-dimensional simplices, and d-dimensional balls.
Recommendations
Cited in
(26)- Dynamic connectivity for axis-parallel rectangles
- Mincut sensitivity data structures for the insertion of an edge
- Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
- Dynamic geometric data structures via shallow cuttings
- Space-efficient fully dynamic DFS in undirected graphs
- Faster randomized worst-case update time for dynamic subgraph connectivity
- Simplified kinetic connectivity for rectangles and hypercubes
- Connectivity oracles for graphs subject to vertex failures
- Dynamic Subgraph Connectivity with Geometric Applications
- New data structures for subgraph connectivity
- Incremental and fully dynamic subgraph connectivity for emergency planning
- scientific article; zbMATH DE number 7559224 (Why is no real title available?)
- Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
- Fully dynamic connectivity oracles under general vertex updates
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Dynamic Connectivity for Axis-Parallel Rectangles
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
- Dynamic connectivity in disk graphs
- Dynamic connectivity in disk graphs
- Dynamic geometric connectivity in the plane with constant query time
- On the complexity of algorithms with predictions for dynamic graph problems
- Fully-adaptive dynamic connectivity of square intersection graphs
- Connectivity oracles for predictable vertex failures
- Dynamic parameterized problems on unit disk graphs
- An optimal 3-fault-tolerant connectivity oracle
This page was built for publication: Dynamic connectivity: connecting to networks and geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3020009)
