New common ancestor problems in trees and directed acyclic graphs

DOI10.1016/j.ipl.2010.02.014zbMath1211.05162OpenAlexW2120291315MaRDI QIDQ991797

Johannes Fischer, Daniel H. Huson

Publication date: 7 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.02.014

zbMATH Keywords

data structuresgraph algorithmscomputational biology

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Directed graphs (digraphs), tournaments (05C20) Computational methods for problems pertaining to biology (92-08)

Related Items (4)

Tree-metrizable HGT networks ⋮ Trinets encode tree-child and level-2 phylogenetic networks ⋮ A cubic-time algorithm for computing the trinet distance between level-1 networks ⋮ Hierarchies from lowest stable ancestors in nonbinary phylogenetic networks

Uses Software

• MEGAN

Cites Work

• Unnamed Item
• Unnamed Item
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• An O(nlog n) Algorithm for the Maximum Agreement Subtree Problem for Binary Trees
• Fast Algorithms for Finding Nearest Common Ancestors
• A Path Cover Technique for LCAs in Dags
• Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
• Fast Lowest Common Ancestor Computations in Dags
• All-Pairs Ancestor Problems in Weighted Dags
• On Finding Lowest Common Ancestors in Trees
• Lowest common ancestors in trees and directed acyclic graphs

This page was built for publication: New common ancestor problems in trees and directed acyclic graphs