Dynamic subgraph connectivity with geometric applications

Research output: Contribution to journalArticlepeer-review

Abstract

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

ASJC Scopus subject areas

  • Software

Fingerprint

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

Cite this