On the reconstruction of binary and permutation matrices under (binary) tomographic constraints

被引：11
作者：
Brunetti, S. [2 ]
Del Lungo, A.
Gritzmann, P. [3 ]
de Vries, S. [1 ]
机构：
[1] Univ Groningen, Fac Econ & Business, Dept Operat, NL-9700 AV Groningen, Netherlands
[2] Univ Siena, Dipartimento Sci Matemat & Informat R Magari, I-53100 Siena, Italy
[3] Tech Univ Munich, Zentrum Math, D-80290 Munich, Germany
来源：
THEORETICAL COMPUTER SCIENCE | 2008年 / 406卷 / 1-2期
关键词：
Combinatorics; Discrete tomography; Queens' problem; Bipartite matching; Contingency table; Binary matrix; Permutation; Computational complexity; NP-hardness;
D O I：
10.1016/j.tcs.2008.06.014
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The paper studies the problem of reconstructing binary matrices constrained by binary tomographic information. We prove new NP-hardness results that sharpen previous complexity results in the realm of discrete tomography but also allow applications to related problems for permutation matrices. Hence our results can be interpreted in terms of other combinatorial problems including the queens' problem. (c) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码：63 / 71
页数：9
相关论文
共 11 条
[1]   On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional X-rays [J].
Brunetti, S ;
Del Lungo, A ;
Gerard, Y .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2001, 339 (1-3) :59-73
[2]  
Even S., 1976, SIAM Journal on Computing, V5, P691, DOI 10.1137/0205048
[3]   A NOTE ON THE QUEENS PROBLEM [J].
FALKOWSKI, BJ ;
SCHMITZ, L .
INFORMATION PROCESSING LETTERS, 1986, 23 (01) :39-46
[4]   On the computational complexity of reconstructing lattice sets from their X-rays [J].
Gardner, RJ ;
Gritzmann, P ;
Prangenberg, D .
DISCRETE MATHEMATICS, 1999, 202 (1-3) :45-71
[5]  
GAREY MR, 1979, COMPUTERS INTRACTABI, P224
[6]   On the algorithmic inversion of the discrete Radon transform [J].
Gritzmann, P ;
de Vries, S .
THEORETICAL COMPUTER SCIENCE, 2002, 281 (1-2) :455-469
[7]  
GRITZMANN P, 1997, LECT NOTES COMPUTER, V1347, P19
[8]  
HERMANN GT, 1999, DISCRETE TOMOGRAPHY
[9]   3-DIMENSIONAL STATISTICAL-DATA SECURITY PROBLEMS [J].
IRVING, RW ;
JERRUM, MR .
SIAM JOURNAL ON COMPUTING, 1994, 23 (01) :170-184
[10]  
Ryser H., 1963, CARUS MATH MONOGRAPH, V14
12