Loading...
research article
On the use of graphs in discrete tomography
In this tutorial paper, we consider the basic image reconstruction problem which stems from discrete tomography. We derive a graph theoretical model and we explore some variations and extensions of this model. This allows us to establish connections with scheduling and timetabling applications. The complexity status of these problems is studied and we exhibit some polynomially solvable cases. We show how various classical techniques of operations research like matching, 2-SAT, network flows are applied to derive some of these results.
Type
research article
Web of Science ID
WOS:000274543100011
Authors
Publication date
2010
Published in
Volume
175
Start page
287
End page
307
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
January 9, 2012
Use this identifier to reference this record