Solving L(2,1)-labeling Problem of Graphs using Genetic Algorithms
1
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (9)
- D. Goncalves, "On the L(p, 1)-labelling of graphs, Discrete Math. and Theor. Comp. Science AE", Discrete Math. and Theor. Comp. Science AE, 81~86 (2005)
- F. S. Roberts, "Working group agenda of DIMACS", DIMATIA, pp.2003, ~
- Gerard J. Change, "Changhong Lu, Distance-two labelings of graphs", Journal of Combinatorics, 24, pp.53~58 (2003)
- Hans L. Bodlaender, "Approximations for λ-coloring of graphs", The Computer Journal, 47, pp.193~204 (2004)
- Holland, J, "Adaptation in Natural and Artificial Systems", University of Michigan Press
- J. R. Griggs, "Labelling graphs with a condition at distance two", SIAM J. Discrete Math, 5, pp.586~595 (1992)
- Oliver, I. M, "A study of permutation crossover operators on the TSP", In Genetic Algorithms and Their Applications: Proceedings of the Second International Conference, pp.224~230
- Pedro Larranaga, "Decomposing Bayesian networks: triangulation of the moral graph with genetic algorithms", Statistics and Computing, 7, pp.19~34 (1997)
- Zbigniew Michalewicz, "Genetic Algorithms + Data Structures=Evolution Programs, Springer-Verlag, Berlin", ~ (1992)