Fulltext

On the use of graphs in discrete tomography

de Werra, Dominique ; Costa, Marie-Christine ; Picouleau, Christophe ; Ries, Bernard

In: 4OR, 2008, vol. 6, no. 2, p. 101-123

Ajouter à la liste personnelle
    Titre
    • On the use of graphs in discrete tomography
    Auteur
    • de Werra, Dominique. ROSE, Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
    • Costa, Marie-Christine. CEDRIC CNAM, Paris, France
    • Picouleau, Christophe. CEDRIC CNAM, Paris, France
    • Ries, Bernard. ROSE, Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
    Type de document
    • Postprint
    Identifiant OAI-PMH
    • oai:doc.rero.ch:321730
    Summary
    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