Reconstructing Binary Matrices underWindow Constraints from their Row and Column Sums

被引：7

作者：

Alpers, Andreas ^{[1
]}

Gritzmann, Peter ^{[1
]}

机构：

[1] Tech Univ Munich, Zentrum Math, D-85747 Garching, Germany

来源：

FUNDAMENTA INFORMATICAE | 2017年 / 155卷 / 04期

关键词：

Tomography; analytical reconstruction algorithms; consistency conditions; TRANSMISSION ELECTRON-MICROSCOPY; DISCRETE TOMOGRAPHY; PROJECTIONS; SETS;

D O I：

10.3233/FI-2017-1588

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The present paper deals with the discrete inverse problem of reconstructing binary matrices from their row and column sums under additional constraints on the number and pattern of entries in specified minors. While the classical consistency and reconstruction problems for two directions in discrete tomography can be solved in polynomial time, it turns out that these window constraints cause various unexpected complexity jumps back and forth from polynomialtime solvability to NP-hardness.

引用

页码：321 / 340

页数：20

共 20 条

[1] Binary vectors partially determined by linear equation systems [J].

Aharoni, R ;

Herman, GT ;

Kuba, A .

DISCRETE MATHEMATICS, 1997, 171 (1-3) :1-16

[2]

Alpers A, 2017, DYNAMIC DISCRE UNPUB

[3]

Alpers A, 2017, UNPUB

[4] 3D particle tracking velocimetry using dynamic discrete tomography [J].

Alpers, Andreas ;

Gritzmann, Peter ;

Moseev, Dmitry ;

Salewski, Mirko .

COMPUTER PHYSICS COMMUNICATIONS, 2015, 187 :130-136

[5]

[Anonymous], 1998, Theory of linear and integer programming

[6]

Cook S. A., 1971, Proceedings of the 3rd annual ACM symposium on theory of computing, P151

[7] RECONSTRUCTING 3-COLORED GRIDS FROM HORIZONTAL AND VERTICAL PROJECTIONS IS NP-HARD: A SOLUTION TO THE 2-ATOM PROBLEM IN DISCRETE TOMOGRAPHY [J].

Duerr, Christoph ;

Guinez, Flavio ;

Matamala, Martin .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (01) :330-352

[8] SETS UNIQUELY DETERMINED BY PROJECTIONS ON AXES .2. DISCRETE CASE [J].

FISHBURN, PC ;

LAGARIAS, JC ;

REEDS, JA ;

SHEPP, LA .

DISCRETE MATHEMATICS, 1991, 91 (02) :149-159

[9] Scanning integer matrices by means of two rectangular windows [J].

Frosini, Andrea ;

Nivat, Maurice ;

Rinaldi, Simone .

THEORETICAL COMPUTER SCIENCE, 2008, 406 (1-2) :90-96

[10] Binary matrices under the microscope: A tomographical problem [J].

Frosini, Andrea ;

Nivat, Maurice .

THEORETICAL COMPUTER SCIENCE, 2007, 370 (1-3) :201-217

← 1 2 →