New common ancestor problems in trees and directed acyclic graphs
DOI10.1016/J.IPL.2010.02.014zbMATH Open1211.05162OpenAlexW2120291315MaRDI QIDQ991797FDOQ991797
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
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
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Computational methods for problems pertaining to biology (92-08)
Cites Work
- Title not available (Why is that?)
- Lowest common ancestors in trees and directed acyclic graphs
- On Finding Lowest Common Ancestors in Trees
- Fast Algorithms for Finding Nearest Common Ancestors
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- 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
- Ultra-succinct representation of ordered trees
- An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
Cited In (8)
- A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
- Trinets encode tree-child and level-2 phylogenetic networks
- An \(O(n\cdot m)\) algorithm for calculating the closure of \(lca\)-type operators.
- The heaviest induced ancestors problem: better data structures and applications
- The lowest common ancestor problem on a tree with an unfixed root
- Hierarchies from lowest stable ancestors in nonbinary phylogenetic networks
- Tree-metrizable HGT networks
- A cubic-time algorithm for computing the trinet distance between level-1 networks
Uses Software
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)
