Permutation reconstruction from MinMax-betweenness constraints

DOI10.1016/J.DAM.2016.03.008zbMATH Open1337.05005arXiv1412.4062OpenAlexW1577591566MaRDI QIDQ290110FDOQ290110

Authors: Irena Rusu 

Publication date: 1 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: In this paper, we investigate the reconstruction of permutations on {1, 2, ..., n} from betweenness constraints involving the minimum and the maximum element located between t and t+1, for all t=1, 2, ..., n-1. We propose two variants of the problem (directed and undirected), and focus first on the directed version, for which we draw up general features and design a polynomial algorithm in a particular case. Then, we investigate necessary and sufficient conditions for the uniqueness of the reconstruction in both directed and undirected versions, using a parameter k whose variation controls the stringency of the betweenness constraints. We finally point out open problems.

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

Recommendations

• Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints
• Permutation reconstruction
• Permutation reconstruction from minors
• Reconstructing permutations from identification minors
• Reconstruction of permutations distorted by reversal errors

zbMATH Keywords

algorithmbetweenness constraintspermutation reconstruction

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations
• Total Ordering Problem
• Fourth IFIP international conference on theoretical computer science -- TCS 2006. IFIP 19th world computer congress, TC-1, foundations of computer science, August 23--24, 2006, Santiago, Chile.

Cited In (6)

• Permutation reconstruction from differences
• Reconstructing permutations from identification minors
• Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints
• Permutation reconstruction from a few large patterns
• Posets and permutations in the duplication-loss model: minimal permutations with \(d\) descents
• Permutation reconstruction from minors

This page was built for publication: Permutation reconstruction from MinMax-betweenness constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290110)