Two Self‐Stabilizing Algorithms for the Maximal Pentagon Partitioning Problem

Abstract

ABSTRACT Given an undirected graph , a collection of disjoint subsets of nodes is called a pentagon partition if each subset satisfies one of the following conditions: (1) and the induced subgraph contains a simple cycle of length 5 (called pentagon ) or (2) . Let denote the set of nodes belonging to subsets satisfying Condition (2). A pentagon partition is called maximal if the induced subgraph contains no pentagon. The problem of finding such a partition is called the Maximal Pentagon Partitioning problem , which is a variant of the graph partitioning problem. In this paper, we propose two self‐stabilizing algorithms to solve the maximal pentagon partitioning problem. The first algorithm assumes a central daemon and distance‐2 model, which converges within moves and each node requires bits of memory. The second algorithm operates under a distributed daemon and distance‐1 model, which converges within rounds and requires bits of memory per node.