Learning Spanning Forests Optimally using CUT Queries in Weighted Undirected Graphs

Hang Liao, Deeparnab Chakrabarty

In this paper we describe a randomized algorithm which returns a maximal spanning forest of an unknown {\em weighted} undirected graph making $O(n)$ $\mathsf{CUT}$ queries in expec…