Degree-constrained edge partitionings in graphs arising from discrete tomography

Bernard Ries; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric

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

Numéro

Pages

99-118

Métadonnées

Afficher la notice complète

Auteur(s)

Bernard Ries
Picouleau, Christophe

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