An Integer Linear Programming Model for Solving Radio Mean Labeling Problem
Autor: | E. M. Badr, Ashraf Eirokh, Sultan Almotairi, Badr Almutairi, Atef Abdel-Hay |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2020 |
Předmět: |
Channel assignment problem
radio mean number General Computer Science Linear programming General Engineering upper bound Natural number Upper and lower bounds Injective function Vertex (geometry) Combinatorics path and cycle Integer Graph (abstract data type) General Materials Science lcsh:Electrical engineering. Electronics. Nuclear engineering Electrical and Electronic Engineering lcsh:TK1-9971 Connectivity Mathematics |
Zdroj: | IEEE Access, Vol 8, Pp 162343-162349 (2020) |
ISSN: | 2169-3536 |
Popis: | 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, ⌈h(x)+h(y)/2⌉ ≥diam+1-d(x, y). The radio mean number of h, rmn(h), is the maximum number assigned 2 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. |
Databáze: | OpenAIRE |
Externí odkaz: |