On the use of graphs in discrete tomography

Abstract : 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. (This paper is an updated version of a tutorial published in 4'OR in 2008.)
Type de document :
Article dans une revue
Annals of Operations Research, Springer Verlag, 2010, 175, pp.287-307. 〈10.1007/s10479-009-0649-6〉
Liste complète des métadonnées

https://hal-ensta.archives-ouvertes.fr/hal-00975034
Contributeur : Aurélien Arnoux <>
Soumis le : lundi 7 avril 2014 - 17:40:31
Dernière modification le : mardi 13 novembre 2018 - 17:10:03

Lien texte intégral

Identifiants

Collections

Citation

Dominique De Werra, Marie-Christine Costa, Christophe Picouleau, Bernard Ries. On the use of graphs in discrete tomography. Annals of Operations Research, Springer Verlag, 2010, 175, pp.287-307. 〈10.1007/s10479-009-0649-6〉. 〈hal-00975034〉

Partager

Métriques

Consultations de la notice

139