On The Span Of A Random Channel Assignment Problem.

Journal article

In the radio channel assignment problems considered here, we must assign a 'channel' from the set 1,2,... of positive integers to each of n transmitters, and we wish to minimise the span of channels used, subject to the assignment leading to an acceptable level of interference. A standard form of this problem is the 'constraint matrix' model. The simplest case of this model (the 0, 1 case) is essentially graph colouring. We consider here a random model for the next simplest case (with lengths 0, 1 or 2), and determine the asymptotic behaviour of the span of channels needed as n→∞. We find that there is a 'phase change' in this behaviour, depending on the probabilities for the different lengths. © Springer-Verlag Berlin Heidelberg 2007.

Authors: McDiarmid, C

• Publication status: Published
• Journal: Combinatorica
• Volume: 27
• Issue: 2
• Pages: 183-203
• Publication date: 2007-01-01
• DOI: 10.1007/s00493-007-0051-4
• EISSN: 1439-6912
• ISSN: 0209-9683
• Language: English