We challenge the problem of the reconstruction of a bicolored domino tiling of a rectangle from its horizontal and vertical projections. We give two NP-completeness results after having defined two non equivalent and very natural notions of projections on a generic bicolored domino tiling. The more general problem of the reconstruction of monochromatic domino tilings is still left open
The reconstruction of a bicolored domino tiling from two projections / A.Frosini; G.Simi. - STAMPA. - 2301:(2002), pp. 136-144. (Intervento presentato al convegno 10th International Conference, DGCI 2002) [10.1007/3-540-45986-3_12].
The reconstruction of a bicolored domino tiling from two projections
FROSINI, ANDREA;
2002
Abstract
We challenge the problem of the reconstruction of a bicolored domino tiling of a rectangle from its horizontal and vertical projections. We give two NP-completeness results after having defined two non equivalent and very natural notions of projections on a generic bicolored domino tiling. The more general problem of the reconstruction of monochromatic domino tilings is still left open
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
[1]congr.pdf
Accesso chiuso
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Tutti i diritti riservati
Dimensione
663.74 kB
Formato
Adobe PDF
|
663.74 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
