The graph is a mathematical structure consisting of vertices and edges. Various problems arising in natural sciences have been modeled and solved by graph structure. In the field of graphs, the Graph Coloring Problem (GCP) is an important, core, and diverse application area. The L(2,1)-cloloring pro...
The graph is a mathematical structure consisting of vertices and edges. Various problems arising in natural sciences have been modeled and solved by graph structure. In the field of graphs, the Graph Coloring Problem (GCP) is an important, core, and diverse application area. The L(2,1)-cloloring problem, which is classified as a Vertex Coloring Problem, has been studied as a field of Frequency Assignment Problem of T-coloring series. In the graph G, finding the optimal solution of L(2,1)-coloring is NP-complete. Therefore, in this paper, we have studied the optimization methods of L(2,1)-coloring using the Meta-Heuristic Algorithm and applied it to the Benchmark graph of DIMACS and BHOSLIB to analyze the effectiveness of the proposed algorithm.
The contents of this study are as follows.
1. The graph G demonstrates that the Greedy Algorithm can generate optimal coloring.
2. The upper bound of L(2,1)-coloring was calculated using the Hamiltonian Path of complement G for DIMACS graphs with diameter 2.
3. Using the Branch and Bound Algorithm, the Hamiltonian path does not exist in the MANN_a9 graph.
4. The lower bound of L(2,1)-coloring is presented by calculating the Maximal Clique of DIMACS and BHOSLIB graphs with diameters of 3 or more.
5. The upper bound of L(2,1)-coloring is proposed using Genetic Algorithm, Simulated Annealing, and Tabu Search, which are classified by Meta-Heuristic algorithm.
6. A Meta-Heuritsic algorithm for nuclear fuel relocation problem based on the degree of combustion has been proposed.
Key words : Graph coloring, L(2,1)-coloring, Meta-Heuristic Algorithm, Genetic Algorithm, Simulated Annealing, Tabu Search, Parallel Processing, Hamiltonian Path, Maximum Clique, Inver-over Algorithm,Branch and Bound Algorithm
The graph is a mathematical structure consisting of vertices and edges. Various problems arising in natural sciences have been modeled and solved by graph structure. In the field of graphs, the Graph Coloring Problem (GCP) is an important, core, and diverse application area. The L(2,1)-cloloring problem, which is classified as a Vertex Coloring Problem, has been studied as a field of Frequency Assignment Problem of T-coloring series. In the graph G, finding the optimal solution of L(2,1)-coloring is NP-complete. Therefore, in this paper, we have studied the optimization methods of L(2,1)-coloring using the Meta-Heuristic Algorithm and applied it to the Benchmark graph of DIMACS and BHOSLIB to analyze the effectiveness of the proposed algorithm.
The contents of this study are as follows.
1. The graph G demonstrates that the Greedy Algorithm can generate optimal coloring.
2. The upper bound of L(2,1)-coloring was calculated using the Hamiltonian Path of complement G for DIMACS graphs with diameter 2.
3. Using the Branch and Bound Algorithm, the Hamiltonian path does not exist in the MANN_a9 graph.
4. The lower bound of L(2,1)-coloring is presented by calculating the Maximal Clique of DIMACS and BHOSLIB graphs with diameters of 3 or more.
5. The upper bound of L(2,1)-coloring is proposed using Genetic Algorithm, Simulated Annealing, and Tabu Search, which are classified by Meta-Heuristic algorithm.
6. A Meta-Heuritsic algorithm for nuclear fuel relocation problem based on the degree of combustion has been proposed.
Key words : Graph coloring, L(2,1)-coloring, Meta-Heuristic Algorithm, Genetic Algorithm, Simulated Annealing, Tabu Search, Parallel Processing, Hamiltonian Path, Maximum Clique, Inver-over Algorithm,Branch and Bound Algorithm
※ AI-Helper는 부적절한 답변을 할 수 있습니다.