Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
417805 | Discrete Applied Mathematics | 2016 | 14 Pages |
Abstract
In this paper, we investigate the reconstruction of permutations on {1,2,…,n}{1,2,…,n} from betweenness constraints involving the minimum and the maximum element located between tt and t+1t+1, for all t=1,2,…,n−1t=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 kk whose variation controls the stringency of the betweenness constraints. We finally point out open problems.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Irena Rusu,