• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail - Request a copy

Degree-constrained edge partitionings in graphs arising from discrete tomography

Bernard Ries; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2009), Degree-constrained edge partitionings in graphs arising from discrete tomography, Journal of Graph Algorithms and Applications, 13, 2, p. 99-118

Type
Article accepté pour publication ou publié
Date
2009
Nom de la revue
Journal of Graph Algorithms and Applications
Volume
13
Numéro
2
Pages
99-118
Métadonnées
Afficher la notice complète
Auteur(s)
Bernard Ries
Picouleau, Christophe cc
de Werra, Dominique
Costa, Marie-Christine
Bentz, Cédric
Résumé (EN)
Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k = 3 colors is open. Variations and special cases are considered for the case k = 3 colors where the graph corresponding to the union of some color classes (for instance colors 1 and 2) has a given structure (tree, vertex-disjoint chains, 2-factor, etc.). We also study special cases corresponding to the search of 2 edge-disjoint chains or cycles going through specied vertices. A variation where the graph is oriented is also presented. In addition we explore similar problems for the case where the underlying graph is a complete graph (instead of a complete bipartite graph).
Mots-clés
tomography; Degree-constrained; vertex disjoint chains; tree; Bipartite graph

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    Reconstruction d'une coloration des arêtes d'un graphe à partir des séquences de degrés 
    Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard (2007) Communication / Conférence
  • Vignette de prévisualisation
    Blockers and transversalsnext term in some previous termsubclasses of bipartite graphs: When caterpillars are dancing on a gridnext term 
    Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    d-Transversals of stable sets and vertex covers in weighted bipartite graphs 
    Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Weighted Transversals and Blockers for Some Optimization Problems in Graphs 
    Ries, Bernard; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2011) Chapitre d'ouvrage
  • Vignette de prévisualisation
    On the use of graphs in discrete tomography 
    de Werra, Dominique; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard (2010) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo