Tree Reconstruction from Partial Orders

DOI10.1137/S0097539793252195MaRDI QIDQ4842119zbMATH OpenOpenAlexFDO

Authors Sampath Kannan, Tandy J. Warnow

Publication date 28 January 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539793252195

zbMATH Keywords

distance matrixedge-weighted treesNP- completeNP-hardpartial orderspath distancepolynomial time algorithmtree reconstruction problem

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07) Analysis of algorithms and problem complexity (68Q25) Computational methods for problems pertaining to biology (92-08) General biology and biomathematics (92B05) Problems related to evolution (92D15) Protein sequences, DNA sequences (92D20)

Recommendations

• Tree reconstruction from partial orders
• On the complexity of ordinal clustering
• A robust model for finding optimal evolutionary tree
• Reconstructing trees from subtree weights.
• An optimal algorithm to reconstruct trees from additive distance data

Cited in

(10)

• On the extension of a partial metric to a tree metric
• Reconstructing trees from subtree weights.
• The triangles method to build X-trees from incomplete distance matrices
• Complexity of splits reconstruction for low-degree trees
• scientific article; zbMATH DE number 3871410 (Why is no real title available?)
• On the complexity of ordinal clustering
• scientific article; zbMATH DE number 1113976 (Why is no real title available?)
• Complexity of splits reconstruction for low-degree trees
• scientific article; zbMATH DE number 1881087 (Why is no real title available?)
• Tree reconstruction from partial orders

This page was built for publication: Tree Reconstruction from Partial Orders

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