A O(m) Self-Stabilizing Algorithm for Maximal Triangle Partition of General Graphs
Abstract
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.
This work is supported by PHC PROCOPE 2015 Program, project id: 33394TD. Research of the second author was funded by the Deutsche Forschungsgemeinschaft (DFG), contract TU 221/6-1.
Communicated by J. Beauquier


