Asymptotic analysis of an assignment problem arising in a distributed communications protocol
- 6 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1455-1459 vol.2
- https://doi.org/10.1109/cdc.1988.194566
Abstract
Matchings for a random bipartite graph are considered. Each of the alpha 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 alpha 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.<>Keywords
This publication has 3 references indexed in Scilit:
- A distributed reservation-based CDMA protocol that does not require feedback informationIEEE Transactions on Communications, 1988
- Average case analysis of Greedy algorithms for Kelly's triangle problem and the independent set problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Maximum matching in sparse random graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981