کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
417805 | 681582 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Permutation reconstruction from MinMaxMinMax-Betweenness constraints
ترجمه فارسی عنوان
بازسازی جایگشت از محدودیت های حداقل حداكثر ـ بینیت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
محدودیت های بین المللی؛ بازسازی جایگشت؛ الگوریتم
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 207, 10 July 2016, Pages 106–119
Journal: Discrete Applied Mathematics - Volume 207, 10 July 2016, Pages 106–119
نویسندگان
Irena Rusu,