"Exists" Connectivity in Graph Timelines
Define a graph timeline to be a sequence of graphs , , , on a common set of vertices of size such that the graph is obtained from 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 and connected by a path in any of , , ,
Parameters
- : number of vertices
- : number of graphs in timeline
- : number of queries
Related Problems
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