A O(m) self-stabilizing algorithm for maximal triangle partition of general fraphs

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.

Subjects

fault-tolerance

Self-stabilizing algorithms

triangle packing

triangle partition

tripartite matching

DDC Class

380: Handel, Kommunikation, Verkehr

Funding(s)

Tolerance-Zone - Fehlertolerante Middleware-Idiome basierend auf selbststabilisierenden Techniken

More Funding Information

Deutsche Forschungsgemeinschaft TU 221/6-1.

Options

A O(m) self-stabilizing algorithm for maximal triangle partition of general fraphs