Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
From MaRDI portal
Publication:3912082
DOI10.1137/0210030zbMath0462.68086OpenAlexW2078109763MaRDI QIDQ3912082
Thomas G. Szymanski, A. V. Aho, Jeffrey D. Ullman, Yehoshua Sagiv
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/948b587696085f55328ca80dfce6380270d1bab1
Related Items
Binets: fundamental building blocks for phylogenetic networks, Compatibility of unrooted phylogenetic trees is FPT, Orthology Relation and Gene Tree Correction: Complexity Results, Counting consistent phylogenetic trees is \#P-complete, Determining phylogenetic networks from inter-taxa distances, Classes of explicit phylogenetic networks and their biological and mathematical significance, Encoding and constructing 1-nested phylogenetic networks with trinets, Some axiomatic limitations for consensus and supertree functions on hierarchies, Closure operations in phylogenetics, Reconstructing phylogenetic trees from multipartite quartet systems, Compatibility, incompatibility, tree-width, and forbidden phylogenetic minors, An efficient algorithm for supertrees, A robust model for finding optimal evolutionary tree, Tree enumeration modulo a consensus, Inferring a level-1 phylogenetic network from a dense set of rooted triplets, Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species, Least resolved trees for two-colored best match graphs, Complexity of modification problems for best match graphs, \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time, Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees, Reconstruction of rooted trees from subtrees, The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets, Graph-theoretic method for merging security system specifications, Kernel and fast algorithm for dense triplet inconsistency, Optimizing tree and character compatibility across several phylogenetic trees, Inducibility in Binary Trees and Crossings in Random Tanglegrams, Best match graphs, Optimizing phylogenetic supertrees using answer set programming, Building a small and informative phylogenetic supertree, Orthology relations, symbolic ultrametrics, and cographs, Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees, Graph triangulations and the compatibility of unrooted phylogenetic trees, Solving infinite-domain CSPs using the patchwork property, Quasi-best match graphs, Caterpillars on three and four leaves are sufficient to binary normal networks, Gene tree correction for reconciliation and species tree inference: complexity and algorithms, The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees, Algebraic dependencies, Tree representations of non-symmetric group-valued proximities, Groves of phylogenetic trees, The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets, Trinets encode orchard phylogenetic networks, New heuristics for rooted triplet consistency, Phylogenetic flexibility via Hall-type inequalities and submodularity, On the weighted quartet consensus problem, Maximum agreement and compatible supertrees, The matroid structure of representative triple sets and triple-closure computation, Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets, On compatibility and incompatibility of collections of unrooted phylogenetic trees, Trinets encode tree-child and level-2 phylogenetic networks, The complexity of reconstructing trees from qualitative characters and subtrees, Constructing the simplest possible phylogenetic network from triplets, Building species trees from larger parts of phylogenomic databases, Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks, New results on optimizing rooted triplets consistency, Fixed-Parameter Algorithms for Finding Agreement Supertrees, Unnamed Item, Unnamed Item, Unnamed Item, An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation, Fast compatibility testing for rooted phylogenetic trees, Reconstructing gene trees from Fitch's xenology relation, Indirect identification of horizontal gene transfer, From Gene Trees to Species Trees through a Supertree Approach, NCHB: a method for constructing rooted phylogenetic networks from rooted triplets based on height function and binarization, A Linear Time Approximation Scheme for Maximum Quartet Consistency on Sparse Sampled Inputs, Reciprocal best match graphs, Reconstructing minimal rooted trees., Three-way symbolic tree-maps and ultrametrics, Combining tree partitioning, precedence, and incomparability constraints, Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time, Best match graphs with binary trees, Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study, Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees, A supertree method for rooted trees, Constraint Satisfaction Problems with Infinite Templates, MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms, Complexity and algorithms for MUL-tree pruning
