Permutation Reconstruction from Differences

Electronic Journal Of Combinatorics

Marzio De Biasi¹ 

关键词: permutation reconstruction;    NP-completeness;   

DOI  :  

学科分类：离散数学和组合数学

来源: Electronic Journal Of Combinatorics

【 摘 要 】

We prove that the problem of reconstructing a permutation $\pi_1,\dotsc,\pi_n$ of the integers $[1\dotso n]$ given the absolute differences $|\pi_{i+1}-\pi_i|$, $i = 1,\dotsc,n-1$ is $\sf{NP}$-complete. As an intermediate step we first prove the $\sf{NP}$

【 授权许可】

Others