Marzio De Biasi

activity

20132017

collaborators

4 papers

cs.CC2017

On the Complexity of Restoring Corrupted Colorings

Marzio De Biasi, Juho Lauri

In the \probrFix problem, we are given a graph $G$ , a (non-proper) vertex-coloring $c : V (G) \to [r]$ , and a positive integer $k$ . The goal is to decide whether a proper $r$ -colori…

cs.CC2014

Permutation Reconstruction from Differences

Marzio De Biasi

We prove that the problem of reconstructing a permutation $π_{1}, \dots, π_{n}$ of the integers $[1 \dots n]$ given the absolute differences $∣ π_{i + 1} - π_{i} ∣$ , $i = 1, \dots, n - 1$ 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…

cs.FL2013

Unary languages recognized by two-way one-counter automata

Marzio De Biasi, Abuzer Yakaryilmaz

A two-way deterministic finite state automaton with one counter (2D1CA) is a fundamental computational model that has been examined in many different aspects since sixties, but we…