Tag Archives: dynamic graphs

Maintaining a random sample of edges on a dynamic graph

Suppose that we have a sample of edges, sampled uniformly at random from the edge set of a graph . Also, let . Now the graph changes, in particular, either a non-existing edge (if the graph is not complete) is inserted or an existing edge is deleted. Do we need to sample edges from scratch?More generally, […]