The Time Complexity of Hsu and Huang's Self-Stabilizing Maximal Matching Algorithm
Masahiro Kimoto, Tatsuhiro Tsuchiya, Tohru Kikuno · IEICE Transactions on Information and Systems · 2010
The exact time complexity of Hsu and Huan's self-stabilizing maximal matching algorithm is provided. It is $\\frac{1}{2}n^2 + n - 2$ if the number of nodes n is even and $\\frac{1}{2}n^2 + n - \\frac{5}{2}$ if n is odd.