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-01-01
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.
| 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.
https://hdl.handle.net/11365/17926
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo