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/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 a combination of several simple ideas. Our method requires Õ(|E| 4ω/(3ω+3)) = O(|E|0.94) amortized update time, and Õ(|E|1/3) query time, after Õ(|E| (5ω+1)/(3ω+3)) preprocessing time, where ω is the matrix multiplication exponent and Õ hides polylogarithmic factors.

Original languageEnglish (US)
Pages (from-to)681-694
Number of pages14
JournalSIAM Journal on Computing
Volume36
Issue number3
DOIs
StatePublished - 2006
Externally publishedYes

Keywords

  • Computational geometry
  • Connectivity
  • Data structures
  • Dynamic graph algorithms

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

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

Cite this