Kernel and fast algorithm for dense triplet inconsistency

DOI10.1016/j.tcs.2012.12.032zbMath1294.68091OpenAlexW2177446487MaRDI QIDQ391097

Sylvain Guillemot, Matthias Mnich

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.12.032

zbMATH Keywords

dense triplet inconsistency

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15)

Related Items (3)

Complexity of modification problems for best match graphs ⋮ Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees ⋮ Constructing a Consensus Phylogeny from a Leaf-Removal Distance (Extended Abstract)

Cites Work

• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Kernels for feedback arc set in tournaments
• New results on optimizing rooted triplets consistency
• Rooted maximum agreement supertrees
• A polynomial time algorithm for the minimum quartet inconsistency problem with \(O(n)\) quartet errors
• Analytic solutions for three taxon ML trees with variable rates across sites
• On problems without polynomial kernels
• The complexity of reconstructing trees from qualitative characters and subtrees
• Constructing the maximum consensus tree from rooted Triples
• A fixed-parameter algorithm for minimum quartet inconsistency
• Extension operations on sets of leaf-labelled trees
• New fixed-parameter algorithms for the minimum quartet inconsistency problem
• Maximum agreement and compatible supertrees
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem
• Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
• Kernel and Fast Algorithm for Dense Triplet Inconsistency
• Fast FAST
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Color-coding
• Determining the Evolutionary Tree Using Experiments
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Aggregating inconsistent information

This page was built for publication: Kernel and fast algorithm for dense triplet inconsistency