Showing 2014 · cs.CCShow all
2 papers · 2 filters
cs.CC2014
Permutation Reconstruction from Differences
Marzio De Biasi
We prove that the problem of reconstructing a permutation of the integers given the absolute differences , is NP-co…
cs.CC2014
Minimal TSP Tour is coNP-Complete
Marzio De Biasi
The problem of deciding if a Traveling Salesman Problem (TSP) tour is minimal was proved to be coNP-complete by Papadimitriou and Steiglitz. We give an alternative proof based on a…