Dynamic Subgraph Connectivity with Geometric Applications

DOI10.1137/S009753970343912XzbMath1120.68057MaRDI QIDQ3446813

Timothy M. Chan

Publication date: 26 June 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

connectivitydata structurescomputational geometrydynamic graph algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Connectivity (05C40)

Related Items

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, On dynamic shortest paths problems, Dynamic connectivity for axis-parallel rectangles, Connectivity Oracles for Graphs Subject to Vertex Failures, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier