A O(m) Self-Stabilizing Algorithm for Maximal Triangle Partition of General Graphs
Brahim Neggazi, Volker Turau, Mohammed Haddad, Hamamache Kheddouci · Parallel Processing Letters · 2017
The triangle partition problem is a generalization of the well-known graph matching problem consisting of finding the maximum number of independent edges in a given graph, i.e., edges with no common node. Triangle partition instead aims to find the maximum number of disjoint triangles. The triangle partition problem is known to be NP-complete. Thus, in this paper, the focus is on the local maximization variant, called maximal triangle partition (MTP). Thus, paper presents a new self-stabilizing algorithm for MTP that converges in O(m) moves under the unfair distributed daemon.