Earticle

초록

영어

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.

한국어

이진트리의 최소 선형 배열(MinLA) 문제의 해는 선형 복잡도 의 근사 알고리즘으로 구하고 있으며, 에 대해 다양한 근사 알고리즘 수행 결과가 제시되어 있고, 단지 2개 알고리즘만이 최적 해 3,696을 얻었다. 본 논문은 이진트리의 정확한 해를 복잡도로 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 먼저, 개 노드들에 중위 탐색(in-order search) 방법으로 번호를 부여하고, 와 레벨에 존재하는 노드들에 대해 단 노드 자식들까지의 범위를 대상으로 번호를 재배열하는 방법을 적용하였다. 제안된 알고리즘을 에 적용한 결과 Chung[14]의 이론을 증명하였으며, 에 대해서는 Chung[14]의 60보다 좋은 58을 얻었다. 또한, 기존의 근사 알고리즘들은 배열 결과를 제시하지 않고 있는데 비해 제안된 알고리즘은 정확한 배열 방법도 제시하는 장점을 갖고 있다. 따라서 제안된 알고리즘은 인 이진트리에 대해서도 항상 빠르게 최적의 해를 얻을 수 있기 때문에 기존의 근사 알고리즘을 적용하지 않아도 된다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 관련 연구와 연구 배경
Ⅲ. 이진트리의 MinLA 알고리즘
Ⅳ. 알고리즘 적용 및 결과 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380