The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees

DOI10.1016/S0166-218X(99)00160-2zbMATH Open0948.05022MaRDI QIDQ1962070FDOQ1962070

Authors Meei Pyng Ng, Nicholas Wormald, Mike Steel 

Publication date 10 April 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

subtreeleaf-labelled tree

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of reconstructing trees from qualitative characters and subtrees
• On the complexity of constructing evolutionary trees
• Finding a maximum compatible tree is NP-hard for sequences and trees
• Convex tree realizations of partitions
• Extension operations on sets of leaf-labelled trees

Cites Work

• scientific article; zbMATH DE number 871930 (Why is no real title available?)
• An efficient algorithm for supertrees
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Reconstruction of rooted trees from subtrees
• The complexity of reconstructing trees from qualitative characters and subtrees

Cited In (6)

• The complexity of reconstructing trees from qualitative characters and subtrees
• The reducts of the homogeneous binary branching \(C\)-relation
• Solving infinite-domain CSPs using the patchwork property
• Recognising the overlap graphs of subtrees of restricted trees is hard
• Determining the consistency of partial tree descriptions
• Convex tree realizations of partitions

This page was built for publication: The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962070)