Permutation reconstruction from MinMax-betweenness constraints
From MaRDI portal
(Redirected from Publication:290110)
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.
Recommendations
Cites work
- 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.
- Total Ordering Problem
- \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations
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)
