The NP-completeness of a tomographical problem on bicolored domino tilings

被引：0

作者：

Frosini, A ^{[1
]}

Simi, G ^{[1
]}

机构：

[1] Univ Siena, Dipartimento Sci Matemat & Informat Roberto Magar, I-53100 Siena, Italy

来源：

THEORETICAL COMPUTER SCIENCE | 2004年 / 319卷 / 1-3期

关键词：

domino tilings; discrete tomography; reconstruction algorithm; computational complexity;

D O I：

10.1016/j.tcs.2004.02.004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：447 / 454

页数：8

共 7 条

[1] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2] Reconstructing polyatomic structures from discrete X-rays:: NP-completeness proof for three atoms
Chrobak, M
Dürr, C
[J]. THEORETICAL COMPUTER SCIENCE, 2001, 259 (1-2) : 81 - 98
[3] STATISTICS OF DIMERS ON A LATTICE .1. NUMBER OF DIMER ARRANGEMENTS ON A QUADRATIC LATTICE
KASTELEYN, P
[J]. PHYSICA, 1961, 27 (12): : 1209 - +
[4] Reconstruction of domino tiling from its two orthogonal projections
Picouleau, C
[J]. THEORETICAL COMPUTER SCIENCE, 2001, 255 (1-2) : 437 - 447
[5] MAPPING PROJECTED POTENTIAL, INTERFACIAL ROUGHNESS, AND COMPOSITION IN GENERAL CRYSTALLINE SOLIDS BY QUANTITATIVE TRANSMISSION ELECTRON-MICROSCOPY
SCHWANDER, P
KISIELOWSKI, C
SEIBT, M
BAUMANN, FH
KIM, Y
OURMAZD, A
[J]. PHYSICAL REVIEW LETTERS, 1993, 71 (25) : 4150 - 4153
[6] DIMER PROBLEM IN STATISTICAL MECHANICS - AN EXACT RESULT
TEMPERLEY, HNV
FISHER, ME
[J]. PHILOSOPHICAL MAGAZINE, 1961, 6 (68): : 1061 - 1063
[7] [No title captured]

← 1 →