1. A O( m) Self-Stabilizing Algorithm for Maximal Triangle Partition of General Graphs.
- Author
-
Neggazi, Brahim, Turau, Volker, Haddad, Mohammed, and Kheddouci, Hamamache
- Subjects
- *
SELF-stabilization (Computer science) , *COMPUTER algorithms , *PARALLEL algorithms , *COMPUTER science , *PARALLEL computers - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF