Dynamic subgraph connectivity with geometric applications

Research output: Contribution to journalConference articlepeer-review


Inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph G = (V, E) and a subset of vertices S ⊆ V, to support insertions and deletions in S and connectivity queries (are two vertices connected?) in the subgraph induced by S. We develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using an elegant combination of several simple ideas. Our method requires linear space, Õ(|E|4ω/(3ω+3)) = O(|E|0.94) amortized update time, and Õ(|E|1/3) query time, where ω is the matrix multiplication exponent and Õ hides polylogarithmic factors.

Original languageEnglish (US)
Pages (from-to)7-13
Number of pages7
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2002
Externally publishedYes
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Dynamic subgraph connectivity with geometric applications'. Together they form a unique fingerprint.

Cite this