Hunting for binary trees in binary character sets : efficient algorithms for extraction, enumeration and optimization
Degree GrantorUniversity of Canterbury
Degree NameResearch report
We describe an efficient solution to a useful variant of the NP-hard Maximum Compatible Subset problem. Let S be a collection of binary characters. We first wish to determine whether there exists a subcollection S' ⊆ S such that S' equals the set of splits of a binary tree. We provide a polynomial time algorithm that solves this problem and also counts how many such subcollections there are. Furthermore, if each of the given characters is weighted, we can efficiently find the subcollection of characters that corresponds to a binary tree and has maximum or minimum summed weight. The algorithm can be extended to deal with subcollections S'⊂ S that correspond to trees with bounded vertex degree, and still have polynomial time efficiency.
- Engineering: Reports