Degree-constrained edge partitioning in graphs arising from discrete tomography

Abstract : Starting from the basic problem of reconstructing a 2-dimensional im- age 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 specified vertices. A variation where the graph is oriented is also presented. In addition we explore similar problems for the case where the under- lying graph is a complete graph (instead of a complete bipartite graph).
Type de document :
Article dans une revue
Journal of Graph Algorithms and Applications (JGAA), Brown University, 2009, 13 (2), pp.99-118. 〈10.7155/jgaa.00178〉
Liste complète des métadonnées

https://hal-ensta.archives-ouvertes.fr/hal-00975345
Contributeur : Aurélien Arnoux <>
Soumis le : mardi 8 avril 2014 - 14:31:59
Dernière modification le : mercredi 6 décembre 2017 - 16:46:01

Lien texte intégral

Identifiants

Collections

Citation

Cédric Bentz, Marie-Christine Costa, Christophe Picouleau, Bernard Ries, Dominique De Werra. Degree-constrained edge partitioning in graphs arising from discrete tomography. Journal of Graph Algorithms and Applications (JGAA), Brown University, 2009, 13 (2), pp.99-118. 〈10.7155/jgaa.00178〉. 〈hal-00975345〉

Partager

Métriques

Consultations de la notice

79