An approximation algorithm for the minimum common supertree problem
Atsuko Yamaguchi, Koji Nakano, Satoru Miyano · Nordic journal of computing · 1997
The minimum common supertree problem is to find a minimum k-ary common supertree for a given set T of labeled complete k-ary trees. This problem is an NP-hard problem. This paper presents a polynomial-time approximation algorithm for solving this problem in O(n3 log n) time, where n is the total number of edges of trees in T. We prove that the algorithm constructs a common supertree that is at most 1 + 1/(2k - 2) times as large as the minimum one.