Showing cs.CCShow all
3 papers · 1 filter
cs.CC2017
On the Complexity of Restoring Corrupted Colorings
Marzio De Biasi, Juho Lauri
In the \probrFix problem, we are given a graph , a (non-proper) vertex-coloring , and a positive integer . The goal is to decide whether a proper -colori…
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…