1-sensitive incremental ss-reach

Given a directed graph G=(V,E)G=(V,E) and a source node sGs \in G, an incremental single-source reachability algorithm maintains the set of nodes reachable from ss (i.e., all nodes vv for which there is a path from ss to vv in the current version of GG) during a sequence of edge insertions, with sensitivity 1, i.e. when 1 edge is inserted.

Parameters

  • nn: number of vertices
  • mm: number of edges

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 1 of 1 reductions

Other relevant algorithms

Insuffient Data to display table