Title :
Asymptotic analysis of an assignment problem arising in a distributed communications protocol
Author_Institution :
Dept. of Electr. Eng., Illinois Univ., Urbana, IL, USA
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
Keywords :
Markov processes; graph theory; packet switching; protocols; assignment problem; asymptotic analysis; distributed communications protocol; ordinary differential equations; random bipartite graph; silent receiver; size matchings; slow Markov random walks; Access protocols; Approximation algorithms; Bipartite graph; Differential equations; H infinity control; Labeling; Packet radio networks; Receivers; Spread spectrum communication;
Conference_Titel :
Decision and Control, 1988., Proceedings of the 27th IEEE Conference on
Conference_Location :
Austin, TX
DOI :
10.1109/CDC.1988.194566
