Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees

DOI10.1016/j.tcs.2015.06.021zbMath1332.68094arXiv1410.2371OpenAlexW2964101983MaRDI QIDQ897856

Simone Linz, Steven Kelk, Leo van Iersel, Nela Lekić

Publication date: 8 December 2015

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

Full work available at URL: https://arxiv.org/abs/1410.2371

zbMATH Keywords

linear ordersphylogenetic treespermutation constraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Permutations, words, matrices (05A05) Total orders (06A05)

Uses Software

• MiniZinc

Cites Work

• Unnamed Item
• Unnamed Item
• Kernel and fast algorithm for dense triplet inconsistency
• Optimizing tree and character compatibility across several phylogenetic trees
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• New results on optimizing rooted triplets consistency
• An improved bound on the maximum agreement subtree problem
• Cyclic ordering is NP-complete
• Constructing the maximum consensus tree from rooted Triples
• The dichromatic number of a digraph
• Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
• The maximum agreement subtree problem
• Domino Tatami Covering Is NP-Complete
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• The complexity of temporal constraint satisfaction problems
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• A Geometric Approach to Betweenness
• The circular chromatic number of a digraph

This page was built for publication: Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees