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 Os and is which show the adjacency constraint, and which can be merged into a single binary matrix.
A., F., C., P., Rinaldi, S. (2008). Reconstructing binary matrices with neighborhood constraints: an NP-hard problem. In Discrete Geometry for Computer Imagery, Proceedings (pp.392-400). Berlin : Springer [10.1007/978-3-540-79126-3_35].
Reconstructing binary matrices with neighborhood constraints: an NP-hard problem
RINALDI, SIMONE
2008-01-01
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 Os and is which show the adjacency constraint, and which can be merged into a single binary matrix.
| File | Dimensione | Formato | |
|---|---|---|---|
|
978-3-540-79126-3_35.pdf
non disponibili
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
435.14 kB
Formato
Adobe PDF
|
435.14 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/431362