A self-stabilizing algorithm for maximal matching in link-register model in $O(n\Delta^3)$ moves - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

## A self-stabilizing algorithm for maximal matching in link-register model in $O(n\Delta^3)$ moves

Laurence Pilard
Johanne Cohen
• Function : Author
Georges Manoussakis
• Function : Author
Devan Sohier
• Function : Author
• PersonId : 993844

#### Abstract

In the matching problem, each node maintains a pointer to one of its neighbor or to $null$, and a maximal matching is computed when each node points either to a neighbor that itself points to it (they are then called married), or to $null$, in which case no neighbor can also point to $null$. This paper presents a self-stabilizing distributed algorithm to compute a maximal matching in the link-register model under read/write atomicity, with complexity {$O(n\Delta^3)$} moves under the adversarial distributed daemon, where $\Delta$ is the maximum degree of the graph.

### Dates and versions

hal-01758068 , version 1 (04-04-2018)

### Identifiers

• HAL Id : hal-01758068 , version 1
• ARXIV :

### Cite

Laurence Pilard, Johanne Cohen, Georges Manoussakis, Devan Sohier. A self-stabilizing algorithm for maximal matching in link-register model in $O(n\Delta^3)$ moves. 2018. ⟨hal-01758068⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

86 View