이진 트리의 최적 2-에지 번호매김에 대한 근사 알고리즘 = Approximation Algorithms for Optimal 2-edge Labeling on Binary Trees

다국어 초록 (Multilingual Abstract)

For a given graph G(V.E). labeling on the graph G is a one-to-one mapping of vertices V into distinct integers. d-edge labeling on the graph G is labeling such that each label is a power of d, when the edge label of an edge is the absolute difference between the labels fob end-vertices of edge.
d-edge labelings on the special classes of tree such as full binary trees and binomial trees have benn investigated, but 2-edge labeling on arbitrary binary trees has not known up to now.
In this thesis, we present the two approximation algorithms of 2-edge labeling on arbitrary binary tress. The time complexities of these algorithms are O(NlgoN) and O(N²logN), respectively. In addtion, we show that the second algorithm obtains the optimal solutions in the every case of experiments.