Computing the rooted triplet distance between galled trees by counting triangles

DOI10.1016/j.jda.2013.10.002zbMath1284.05293OpenAlexW2077072317MaRDI QIDQ2442817

Andrzej Lingas, Jesper Jansson

Publication date: 1 April 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2013.10.002

zbMATH Keywords

graph algorithmmatrix multiplicationtriangle countingphylogenetic network comparisonrooted triplet distance

Mathematics Subject Classification ID

Problems related to evolution (92D15) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (6)

An efficient algorithm for the rooted triplet distance between galled trees ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ Algorithms for visualizing phylogenetic networks ⋮ Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets ⋮ A cubic-time algorithm for computing the trinet distance between level-1 networks ⋮ Computing the rooted triplet distance between phylogenetic networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On encodings of phylogenetic networks of bounded level
• Constructing the simplest possible phylogenetic network from triplets
• Comparing and aggregating partially resolved trees
• Finding and counting given length cycles
• All that glisters is not galled
• Fixed topology alignment with recombination
• Computing the maximum agreement of phylogenetic networks
• Fast Algorithms for Finding Nearest Common Ancestors
• Multiplying matrices faster than coppersmith-winograd
• Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
• Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree

This page was built for publication: Computing the rooted triplet distance between galled trees by counting triangles