New common ancestor problems in trees and directed acyclic graphs

DOI10.1016/J.IPL.2010.02.014MaRDI QIDQ991797zbMATH OpenOpenAlexFDO

Authors Johannes Fischer, D. 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 structurescomputational biologygraph algorithms

Mathematics Subject Classification ID

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

Recommendations

• Lowest common ancestors in trees and directed acyclic graphs
• On two restricted ancestors tree problems
• Finding least common ancestors in directed acyclic graphs
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Finding lowest common ancestors in arbitrarily directed trees
• Ancestor problem for branching trees
• The lowest common ancestor problem on a tree with an unfixed root
• All-Pairs Ancestor Problems in Weighted Dags
• Arborescence problems in directed graphs: theorems and algorithms
• On a directed tree problem motivated by a newly introduced graph product

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• A Path Cover Technique for LCAs in Dags
• All-Pairs Ancestor Problems in Weighted Dags
• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast Lowest Common Ancestor Computations in Dags
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Lowest common ancestors in trees and directed acyclic graphs
• On Finding Lowest Common Ancestors in Trees
• Ultra-succinct representation of ordered trees
• Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication

Cited in

(8)

• A cubic-time algorithm for computing the trinet distance between level-1 networks
• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Hierarchies from lowest stable ancestors in nonbinary phylogenetic networks
• The lowest common ancestor problem on a tree with an unfixed root
• Trinets encode tree-child and level-2 phylogenetic networks
• Tree-metrizable HGT networks
• The heaviest induced ancestors problem: better data structures and applications
• An \(O(n\cdot m)\) algorithm for calculating the closure of \(lca\)-type operators.

Describes a project that uses

Uses Software

• MEGAN

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

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