Article ID Journal Published Year Pages File Type
417805 Discrete Applied Mathematics 2016 14 Pages PDF
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
,