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.
The NP-completeness of a tomographical problem on bicolored domino tilings / A. FROSINI; G.SIMI. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 319/1-3:(2004), pp. 447-454. [10.1016/j.tcs.2004.02.004]
The NP-completeness of a tomographical problem on bicolored domino tilings
FROSINI, ANDREA;
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
