Abstract
Matchings for a random bipartite graph are considered. Each of the αM nodes on one side of the graph is directly connected to Q nodes chosen randomly and uniformly from among the M nodes on the other side of the graph. The size matchings found by two simple approximation algorithms, as well as the size of the maximum matching when Q = 2, are asymptotically determined in the limit as Q tends to infinity with α fixed. The work is motivated by a distributed communications protocol for accessing a silent receiver. The theory of approximating slow Markov random walks by ordinary differential equations is used for the analysis.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1455-1459 |
| Number of pages | 5 |
| Journal | Proceedings of the IEEE Conference on Decision and Control |
| State | Published - 1988 |
| Event | Proceedings of the 27th IEEE Conference on Decision and Control - Austin, TX, USA Duration: Dec 7 1988 → Dec 9 1988 |
ASJC Scopus subject areas
- Control and Systems Engineering
- Modeling and Simulation
- Control and Optimization