• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

On the use of graphs in discrete tomography

Thumbnail
Date
2010
Notes
également publié dans "4OR: A Quarterly Journal of Operations Research", vol. 6, num. 2, 2008
Dewey
recherche opérationnelle
Sujet
Edge coloring; Complete bipartite graph; Discrete tomography; Scheduling; Constrained coloring; Timetabling
Journal issue
Annals of Operations Research
Volume
175
Publication date
2010
Article pages
287-307
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s10479-009-0649-6
URI
https://basepub.dauphine.fr/handle/123456789/6030
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
de Werra, Dominique
Costa, Marie-Christine
Picouleau, Christophe
Ries, Bernard
Type
Article accepté pour publication ou publié
Abstract (EN)
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.