In this paper we study the problem of reconstructing a bicolored domino tiling of a rectangular surface from its horizontal and vertical projections. We use a reduction from the NP-complete problem NUMERICAL MATCHING WITH TARGET SUMS in order to prove that, unless P = NP, this task cannot be performed in polynomial time. The reconstruction of monochromatic domino tilings is still open.

Frosini, A., & Simi, G. (2004). The NP-Completeness of a Tomographical problem on bicolorede domino tilings. THEORETICAL COMPUTER SCIENCE, 319, 447-454.

The NP-Completeness of a Tomographical problem on bicolorede domino tilings

SIMI, GIULIA
2004

Abstract

In this paper we study the problem of reconstructing a bicolored domino tiling of a rectangular surface from its horizontal and vertical projections. We use a reduction from the NP-complete problem NUMERICAL MATCHING WITH TARGET SUMS in order to prove that, unless P = NP, this task cannot be performed in polynomial time. The reconstruction of monochromatic domino tilings is still open.
Frosini, A., & Simi, G. (2004). The NP-Completeness of a Tomographical problem on bicolorede domino tilings. THEORETICAL COMPUTER SCIENCE, 319, 447-454.
File in questo prodotto:
File Dimensione Formato  
The NP-Completeness of a ....pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 197.39 kB
Formato Adobe PDF
197.39 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/17926
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo