An upper bound of radio k-coloring problem and its integer linear programming model
| Autor: | Mahmoud Moussa, E. M. Badr |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Integer linear programming model
Computer Networks and Communications Computer science 020206 networking & telecommunications 020302 automobile design & engineering 02 engineering and technology Solver Polynomial algorithm Upper and lower bounds Graph Vertex (geometry) Combinatorics 0203 mechanical engineering 0202 electrical engineering electronic engineering information engineering Path graph Electrical and Electronic Engineering Coloring problem Connectivity Information Systems |
| Zdroj: | Wireless Networks. 26:4955-4964 |
| ISSN: | 1572-8196 1022-0038 |
| Popis: | For a positive integer k, a radio k-coloring of a simple connected graph G = (V(G), E(G)) is a mapping $$f:V(G) \to \{ 0,1,2, \ldots \}$$ such that $$|f(u) - \,f(v)| \ge k + 1 - d(u, \, v)$$ for each pair of distinct vertices u and v of G, where d(u, v) is the distance between u and v in G. The span of a radio k-coloring f, rck(f), is the maximum integer assigned by it to some vertex of G. The radio k-chromatic number, rck(G) of G is min{rck(f)}, where the minimum is taken over all radio k-colorings f of G. If k is the diameter of G, then rck(G) is known as the radio number of G. In this paper, we propose an improved upper bound of radio k-chromatic number for a given graph against the other which is due to Saha and Panigrahi (in: Arumugan, Smyth (eds) Combinatorial algorithms (IWOCA 2012). Lecure notes in computer science, vol 7643, Springer, Berlin, 2012). The computational study shows that the proposed algorithm overcomes the previous algorithm. We introduce a polynomial algorithm [differs from the other that is due to Liu and Zhu (SIAM J Discrete Math 19(3):610–621, 2005)] which determines the radio number of the path graph Pn. Finally, we propose a new integer linear programming model for the radio k-coloring problem. The computational study between the proposed algorithm and LINGO solver shows that the proposed algorithm overcomes LINGO solver. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink