"Exists" Connectivity in Graph Timelines

Define a graph timeline to be a sequence of graphs G1G_1, G2G_2, \dots, GtG_t on a common set of vertices VV of size nn such that the graph GiG_i is obtained from Gi1G_{i-1} by adding or deleting a single edge. Given a graph timeline, preprocess the timeline to build a data structure that may answer "exists" connectivity queries of the form: are vertices uu and vv connected by a path in any of GaG_a, Ga+1G_{a+1} ,\dots ,GbG_b

Parameters

  • nn: number of vertices
  • tt: number of graphs in timeline
  • qq: number of queries

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 2 of 2 reductions

Other relevant algorithms

Insuffient Data to display table