#### Title

Maximum matching for anonymous trees with constant space per process

#### Document Type

Conference Proceeding

#### Abstract

We give a silent self-stabilizing protocol for computing a maximum matching in an anonymous network with a tree topology. The round complexity of our protocol is O(diam), where diam is the diameter of the network, and the step complexity is O(n diam), where n is the number of processes in the network. The working space complexity is O(1) per process, although the output necessarily takes O(log δ) space per process, where δ is the degree of that process. To implement parent pointers in constant space, regardless of degree, we use the cyclic Abelian group ℤ7. © Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa.

#### Citation Information

Datta, A.,
Larmore, L.,
Masuzawa, T.
(2016).
Maximum matching for anonymous trees with constant space per process.
*Leibniz International Proceedings in Informatics, LIPIcs, 46*
16.1-16.16.
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.

http://dx.doi.org/10.4230/LIPIcs.OPODIS.2015.16