1 paper
Krzysztof Onak, Dana Ron, Michal Rosen +1
We give a nearly optimal sublinear-time algorithm for approximating the size of a minimum vertex cover in a graph G. The algorithm may query the degree deg(v) of any vertex v of it…