Frequency Channel Assignment on Planar Networks

摘要

For integers p ≥ q, a L(p, q)-labeling of a network G is an integer labeling of the nodes of G such that adjacent nodes receive integers which differ by at least p, and nodes at distance two receive labels which differ by at least q. The minimum number of labels required in such labeling is λ_q~p(G). This arises in the context of frequency channel assignment in mobile and wireless networks and often G is planar. We show that if G is planar then λ_q~p(G) ≤ 5/3 (2q ― 1)Δ + 12p + 144q - 78. We also provide an O(n~2) time algorithm to find such a labeling. This provides a (5/3 +o(1))-approximation algorithm for the interesting case of q = 1, improving the best previous approximation ratio of 2.