Finding a maximal or maximum matching in a graph is a well-understood problem for which efficient sequential algorithms exist. Applications of matchings in distributed settings make it desirable to find self-stabilizing asynchronous distributed solutions to these problems. We first present a self-stabilizing algorithm for finding a maximal matching in a general anonymous network under read/write atomicity with linear round complexity. This is followed by a self-stabilizing algorithm, with quadratic time complexity, for finding a maximum matching in a bipartite network under composite atomicity. These results represent significant progress in the area of distributed algorithms for matchings.

There is considerable interest in constructing large networks with given diameter and maximum degree. In certain applications, there is a natural restriction for the networks to be planar. Thus, consider the problem of determining the maximum number of nodes in a planar network with maximum degree Δ and diameter at most k. We have previously proved that this number is at most (roughly) 12kΔ⌊k/2⌋ and there is a trivial lower bound of about (Δ − 1)⌊k/2⌋. We introduce a number of general constructions which substantially improve the lower bound and yield the largest known networks. We also provide a catalog of the best-known networks for small values of Δ and k, many obtained by specialized constructions. © 1998 John Wiley & Sons, Inc. Networks 32:275–281, 1998