On the use of graphs in discrete tomography

Dominique de Werra, Marie-Christine Costa, Christophe Picouleau and 
Bernard Ries
march, 2010
Type de publication :
Article (revues avec comité de lecture)
Journal :
Annals of Operations Research, vol. 175, pp. 287-307
Editeur :
Mots clés :
discrete tomography, complete bipartite graph, edge coloring, timetabling, constrained coloring, scheduling
Résumé :
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.)
BibTeX :
    author={Dominique de Werra and Marie-Christine Costa and Christophe 
           Picouleau and Bernard Ries },
    title={On the use of graphs in discrete tomography },
    doi={10.1007/s10479-009-0649-6 },
    journal={Annals of Operations Research },
    year={2010 },
    volume={175 },