Nordic Journal of Computing Bibliography

Atsuko Yamaguchi, Koji Nakano, and Satoru Miyano. An Approximation Algorithm for the Minimum Common Supertree Problem. Nordic Journal of Computing, 4(3):303-316, Fall 1997.
Abstract

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.

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


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database