[1]} describe the use of weights that are exponential in \(n\)  (henceforth exponential weights) in order to find a rank-maximal stable matching using a maximum weight approach. This requires an additional factor of \(O(n)\)  time complexity to take into account calculations over exponential weights, giving an overall time complexity of \(O(nm^2 \log n)\)  [1]} actually state a time complexity of \(O(nm^2 \log n \log n)\) , however, we believe that this time complexity bound is somewhat pessimistic and that a bound of \(O(nm^2 \log n)\)  applies to this approach..
[1]}'s approach (described in more detail in Section ) requires a Max Flow algorithm to be used. [1]} stated that the strongly polynomial \(O(m^2 \log n)\)  Sleator-Tarjan algorithm [5]} was the best option (at the time of writing). The Sleator-Tarjan algorithm [5]} is an adapted version of [7]}'s algorithm [7]} and finds a maximum flow in a network in \(O(|V||E| \log |V|)\)  time. Since \(|V| \le m\) , \(|E| \le m\)  and \(O(\log m)\)  is equivalent to \(O(\log n)\)  [9]}, this translates to \(O(m^2 \log n)\)  for the maximum weight stable matching problem and an overall time complexity of \(O(nm^2 \log n)\)  for the rank-maximal stable matching problem. However in [10]} [10]} described an improved strongly polynomial Max Flow algorithm with an \(O(|V||E|)\)  (translating to \(O(m^2)\) ) time complexity, giving a total overall time complexity for finding a rank-maximal stable matching of \(O(nm^2)\) . [12]}'s weighted sat approach [12]} has an overall \(O(n^{0.5}m^{1.5})\)  time complexity for finding a rank-maximal stable matching.
Neither [1]} nor [12]} considered generous stable matchings, however, a generous stable matching may be found in a similar way to a rank-maximal stable matching with the use of exponential weights.
