An algorithm for finding a representation of a subtree distance

DOI10.1007/978-3-319-45587-7_22MaRDI QIDQ2835681zbMATH OpenOpenAlexFDO

Authors Kazutoshi Ando, Koki Sato

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-45587-7_22

zbMATH Keywords

phylogenyrealization algorithmtree metrics

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Problems related to evolution (92D15)

Recommendations

• An algorithm for finding a representation of a subtree distance
• Characterization of the distance between subtrees of a tree by the associated tight span
• An algorithm for tree-realizability of distance matrices^∗
• A fast algorithm for constructing trees from distance matrices
• A 3-approximation algorithm for the subtree distance between phylogenies

Cites work

• A fast algorithm for constructing trees from distance matrices
• A note on the metric properties of trees
• Characterization of the distance between subtrees of a tree by the associated tight span
• Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees

Cited in

(3)

• An algorithm for finding a representation of a subtree distance
• Characterization of the distance between subtrees of a tree by the associated tight span
• Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance

This page was built for publication: An algorithm for finding a representation of a subtree distance

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