AbstractThe 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.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: approximation algorithm, NP-complete, minimum common supertree problem, labeled trees
Selected references
- Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis. Linear approximation of shortest superstrings. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 328-336, New Orleans, Louisiana, 6-8 May 1991.
- John Gallant, David Maier, and James A. Storer. On finding minimal length superstrings. Journal of Computer and System Sciences, 20(1):50-58, February 1980.
- Ming Li. Towards a DNA sequencing theory (learning a string) (preliminary version). In 31st Annual Symposium on Foundations of Computer Science, volume I, pages 125-134, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15(4):1036-1053, November 1986.
- Jorma Tarhio and Esko Ukkonen. A greedy approximation algorithm for constructing shortest common superstrings. Theoretical Computer Science, 57(1):131-145, April 1988.
- Jonathan S. Turner. Approximation algorithms for the shortest common superstring problem. Information and Computation, 83(1):1-20, October 1989.
- Esko Ukkonen. A linear-time algorithm for finding approximate shortest common superstrings. Algorithmica, 5:313-323, 1990.
- Tandy J. Warnow. Tree compatibility and inferring evolutionary history. Journal of Algorithms, 16(3):388-407, May 1994.