:: The Journal of the Institute of Internet, Broadcasting and Communication ::, Vol.24 No.2 | (2024) pp.99~104
이진트리의 최소선형배열 알고리즘
Abstract
이진트리의 최소 선형 배열(MinLA) 문제의 해는 선형 복잡도 의 근사 알고리즘으로 구하고 있으며, 에 대해 다양한 근사 알고리즘 수행 결과가 제시되어 있고, 단지 2개 알고리즘만이 최적 해 3,696을 얻었다. 본 논문은 이진트리의 정확한 해를 복잡도로 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 먼저, 개 노드들에 중위 탐색(in-order search) 방법으로 번호를 부여하고, 와 레벨에 존재하는 노드들에 대해 단 노드 자식들까지의 범위를 대상으로 번호를 재배열하는 방법을 적용하였다. 제안된 알고리즘을 에 적용한 결과 Chung[14]의 이론을 증명하였으며, 에 대해서는 Chung[14]의 60보다 좋은 58을 얻었다. 또한, 기존의 근사 알고리즘들은 배열 결과를 제시하지 않고 있는데 비해 제안된 알고리즘은 정확한 배열 방법도 제시하는 장점을 갖고 있다. 따라서 제안된 알고리즘은 인 이진트리에 대해서도 항상 빠르게 최적의 해를 얻을 수 있기 때문에 기존의 근사 알고리즘을 적용하지 않아도 된다.
In the deficiency of an exact solution yielding algorithm, approximate algorithms remain as a solely viable option to the Minimum Linear Arrangement(MinLA) problem of Binary tree. Despite repeated attempts by a number of algorithm on , only two of them have been successful in yielding the optimal solution of 3,696. This paper therefore proposes an algorithm of complexity that delivers the exact solution to the binary tree. The proposed algorithm firstly employs an In-order search method by which number of nodes are assigned with a distinct number. Then it reassigns the number of all nodes that occur on level and , including that of child of leaf node. When applied to , the proposed algorithm has proven Chung[14]’s conjecture and obtained a superior result. Moreover, on the contrary to existing algorithms, the proposed algorithm illustrates a detailed assignment method. Capable of expeditiously obtaining the optimal solution for the binary tree of , the proposed algorithm could replace the existing approximate algorithms.
Minimum linear arrangement,Optimal linear ordering,Layout problem,Lattice,Mesh
