Algorithms for Finding the Largest Subtree whose Copies Cover All the Leaves

Tatsuya AKUTSU  Satoshi KOBAYASHI  Koichi HORI  Setsuo OHSUGA  

IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.6   pp.707-710
Publication Date: 1993/06/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm and Computational Complexity
algorithms,  macro operator,  learning,  graph algorithms,  subtree,  

Full Text: PDF(241.8KB)>>
Buy this Article

This paper presents efficient algorithms for finding the largest tree S such that there are vertex disjoint subtrees S1, , S (k1) of T each of which is isomorphic to S and every leaf of T is a leaf of some Si. The algorithms are useful for learning a macro table.