1-2hit |
Masahiro KIMOTO Tatsuhiro TSUCHIYA Tohru KIKUNO
The exact time complexity of Hsu and Huan's self-stabilizing maximal matching algorithm is provided. It is n2 + n - 2 if the number of nodes n is even and n2 + n - if n is odd.
Masahiro KIMOTO Tatsuhiro TSUCHIYA Tohru KIKUNO
In this letter we give a lower bound on the worst-case time complexity of Dijkstra's three-state mutual exclusion algorithm by specifying a concrete behavior of the algorithm. We also show that our result is more accurate than the known best bound.