Show simple item record

Tile-Packing Tomography Is NP-hard

dc.contributor.authorChrobak, Marek
dc.contributor.authorDürr, Christoph
HAL ID: 5030
ORCID: 0000-0001-8103-5333
dc.contributor.authorGuinez, Flavio
dc.contributor.authorLozano, Antoni
dc.contributor.authorThang, Nguyen Kim
dc.date.accessioned2011-04-26T14:31:14Z
dc.date.available2011-04-26T14:31:14Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6051
dc.language.isoenen
dc.subjectTilingsen
dc.subjectDiscrete tomographyen
dc.subjectNP-hardnessen
dc.subjectAffine independenceen
dc.subject.ddc003en
dc.titleTile-Packing Tomography Is NP-harden
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenDiscrete tomography deals with reconstructing finite spatial objects from their projections. The objects we study in this paper are called tilings or tile-packings, and they consist of a number of disjoint copies of a fixed tile, where a tile is defined as a connected set of grid points. A row projection specifies how many grid points are covered by tiles in a given row; column projections are defined analogously. For a fixed tile, is it possible to reconstruct its tilings from their projections in polynomial time? It is known that the answer to this question is affirmative if the tile is a bar (its width or height is 1), while for some other types of tiles NP -hardness results have been shown in the literature. In this paper we present a complete solution to this question by showing that the problem remains NP-hard for all tiles other than bars.en
dc.relation.isversionofjnlnameAlgorithmica
dc.relation.isversionofjnlvol64
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages267-278
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s00453-011-9498-1en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail
Name:
tile_packing.PDF
Size:
184.7Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record