This paper deals with the reconstruction of binary matrices having exactly - 1 - 4 - adjacency constraints from the horizontal and vertical projections. Such a problem is shown to be non polynomial by means of a reduction which involves the classic NP-complete problem 3- color. The result is reached by bijectively mapping all the four different cells involved in 3-color into maximal configurations of 0s and 1s which show the adjacency constraint, and which can be merged into a single binary matrix.
Reconstructing Binary Matrices with Neighborhood Constraints: an NP-hard problem / A. Frosini; C. Picouleau; S. Rinaldi. - STAMPA. - 4992:(2008), pp. 392-400. (Intervento presentato al convegno Discrete Geometry and Computational Imagery).
Reconstructing Binary Matrices with Neighborhood Constraints: an NP-hard problem
FROSINI, ANDREA;
2008
Abstract
This paper deals with the reconstruction of binary matrices having exactly - 1 - 4 - adjacency constraints from the horizontal and vertical projections. Such a problem is shown to be non polynomial by means of a reduction which involves the classic NP-complete problem 3- color. The result is reached by bijectively mapping all the four different cells involved in 3-color into maximal configurations of 0s and 1s which show the adjacency constraint, and which can be merged into a single binary matrix.
| File | Dimensione | Formato | |
|---|---|---|---|
|
[14]congr.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
420.26 kB
Formato
Adobe PDF
|
420.26 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
