An Integer Linear Programming Model for Solving Radio Mean Labeling Problem

Abstract

A Radio mean labeling of a connected graph $G$ is an injective function $h$ from the vertex set, $V(G)$ , to the set of natural numbers $N$ such that for any two distinct vertices $x$ and $y$ of $G$ , $\left \lceil{ \frac {h\left ({x }\right)+h(y)}{2} }\right \rceil \mathrm {\ge }diam\mathrm {+1-}d(x,y)$ . The radio mean number of $h$ , $rmn(h)$ , is the maximum number assigned to any vertex of $G$ . The radio mean number of $G$ , $rmn(G)$ , is the minimum value of $rmn(h)$ , taken over all radio mean labeling $h$ of $G$ . This work has three contributions. The first one is proving two theorems which find the radio mean number for cycles and paths. The second contribution is proposing an approximate algorithm which finds an upper bound for radio mean number of a given graph. The third contribution is that we introduce a novel integer linear programing formulation for the radio mean problem. Finally, the experimental results analysis and statistical test proved that the Integer Linear Programming Model overcame the proposed approximate algorithm according to CPU time only. On the other hand, both the Integer Linear Programming Model and the proposed approximate algorithm had the same upper bound of the radio mean number of $G$ .

Keywords

• Channel assignment problem
• radio mean number
• upper bound
• path and cycle