Dynamic connectivity for axis-parallel rectangles
type: Item
instance of: scholarly article
title: Dynamic connectivity for axis-parallel rectangles
zbMATH Open document ID: 1184.68196
author: Peyman Afshani
author: Timothy M. Chan
published in: Algorithmica
publication date: 2009-05-06T00:00:00Z
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 5551241
zbMATH Keywords: data structures
zbMATH Keywords: dynamic data structures
zbMATH Keywords: computational geometry
zbMATH Keywords: dynamic connectivity
MaRDI profile type: Publication
full work available at URL: s00453-008-9234-7
OpenAlex ID: W2082803170
cites work: Q4225298
cites work: Semi-Online Maintenance of Geometric Optima and Measures
cites work: Dynamic Subgraph Connectivity with Geometric Applications
cites work: Applications of random sampling in computational geometry. II
cites work: Matrix multiplication via arithmetic progressions
cites work: Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n 2 barrier
cites work: Lower bounds for fully dynamic connectivity problems in graphs
cites work: Algorithms for generalized halfspace range searching and other intersection searching problems
cites work: Randomized fully dynamic graph algorithms with polylogarithmic time per operation
cites work: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
cites work: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
cites work: A fully dynamic algorithm for maintaining the transitive closure
cites work: Logarithmic Lower Bounds in the Cell-Probe Model
cites work: Q4471323
cites work: A fully dynamic reachability algorithm for directed graphs with an almost linear update time
cites work: Decremental Dynamic Connectivity
cites work: Near-optimal fully-dynamic graph connectivity
DOI: 10.1007/S00453-008-9234-7
Recommended article: Dynamic Connectivity for Axis-Parallel Rectangles
Recommended article: Semi-dynamic Connectivity in the Plane
Recommended article: Simplified kinetic connectivity for rectangles and hypercubes
Recommended article: Dynamic Connectivity: Connecting to Networks and Geometry
Recommended article: Dynamic Subgraph Connectivity with Geometric Applications
Recommended article: Fully Dynamic Algorithms for 2-Edge Connectivity
Recommended article: Static and dynamic parallel computation of connected components
Recommended article: Fully dynamic 2-edge-connectivity in planar graphs
Recommended article: A topological approach to dynamic graph connectivity
description: scientific article; zbMATH DE number 5551241