Optimal non-adaptive algorithm for edge estimation

Arijit Bishnu, Debarshi Chanda, Buddha Dev Das +2

We present a simple nonadaptive randomized algorithm that estimates the number of edges in a simple, unweighted, undirected graph, possibly containing isolated vertices, using only…