On the Optimality of an Algorithm of Reingold and Supowit
Peter J. Grabner, Helmut Prodinger · Journal of automata, languages and combinatorics · 1996
In [5], Reingold and Supowit have analyzed a divide-and-conquer heuristic to obtain a matching with a small cost. In this paper we show that -- among a large class of similar strategies -- the version of Reingold and Supowit produces the minimal expected costs.