Before revision:  We present an algorithm that, if one knows the number of required samples q in advance, has an overall cost of O^*(\sqrt q \cdot(n/\sqrt m)), which is strictly preferable to O^*(q\cdot (n/\sqrt m)) cost resulting from q invocations of the algorithm by Eden and Rosenbaum . More generally, for an input parameter x>1, our algorithm has a preprocessing phase with O^*(n/(x\cdot d_{avg)) cost, which then allows an O(x/\epsilon) per-sample cost, where d_{avg} denotes the average degree of the graph} .
After revision:  We present an algorithm that, if one knows the number of required samples q in advance, has an overall cost of O^*(\sqrt q \cdot(n/\sqrt m)), which is strictly preferable to O^*(q\cdot (n/\sqrt m)) cost resulting from q invocations of the algorithm by Eden and Rosenbaum )) cost, which then allows an O(x/\epsilon) per-sample cost, where d_{avg} denotes the average degree of the graph} .