Convex tree realizations of partitions

0.00 Avg rating—0 Votes

Article ID:	iaor19932354
Country:	United Kingdom
Volume:	5
Start Page Number:	3
End Page Number:	6
Publication Date:	Dec 1992
Journal:	Applied Mathematics Letters
Authors:	Dress Andreas, Steel Michael
Keywords:	combinatorial analysis, computational analysis

Abstract:

Given a collection P of partitions of a label set L a problem arising in biological and linguistic classification is deciding whether there is a ‘tree-structure’ on L which is ‘compatible’ with P. While this problem is, in general, NP-complete the authors show that it has a polynomial time solution if the number of sets in each partition is at most three.

Reviews

Required fields are marked *. Your email address will not be published.