Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints

DOI10.1016/j.jda.2018.05.001zbMath1400.68150OpenAlexW2805270032MaRDI QIDQ1784981

Irena Rusu, Léo Pelletier

Publication date: 27 September 2018

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2018.05.001

zbMATH Keywords

algorithmpermutationbetweennesscommon intervals

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Permutations, words, matrices (05A05)

Uses Software

• CREx

Cites Work

• Permutation reconstruction from MinMax-betweenness constraints
• Common intervals of multiple permutations
• Fast algorithms to enumerate all common intervals of two permutations
• \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations
• On the Similarity of Sets of Permutations and Its Applications to Genome Comparison
• Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs
• On the Approximability of Comparing Genomes with Duplicates
• Total Ordering Problem
• Algorithms and Computation