Solving L(2,1)-Labeling Problem of Graphs using Genetic Algorithms


The KIPS Transactions:PartB , Vol. 15, No. 2, pp. 131-136, Apr. 2008
10.3745/KIPSTB.2008.15.2.131,   PDF Download:

Abstract

L(2,1)-labeling of a graph G is a function f: V(G) → {0, 1, 2, ...} such that f(u) ? f(v) ≥ 2 when d(u, v) = 1 and f(u) ? f(v) ≥ 1 when d(u, v) = 2. L(2,1)-labeling number of G, denoted by λ(G), is the smallest number m such that G has an L(2,1)-labeling with no label greater than m. Since this problem has been proved to be NP-complete, in this article, we develop genetic algorithms for L(2,1)-labeling problem and show that the suggested genetic algorithm peforms very efficiently by applying the algorithms to the class of graphs with known optimum values.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
K. H. Han and C. S. Kim, "Solving L(2,1)-Labeling Problem of Graphs using Genetic Algorithms," The KIPS Transactions:PartB , vol. 15, no. 2, pp. 131-136, 2008. DOI: 10.3745/KIPSTB.2008.15.2.131.

[ACM Style]
Keun Hee Han and Chan Soo Kim. 2008. Solving L(2,1)-Labeling Problem of Graphs using Genetic Algorithms. The KIPS Transactions:PartB , 15, 2, (2008), 131-136. DOI: 10.3745/KIPSTB.2008.15.2.131.