[BCP09] Degree-constrained edge partitioning in graphs arising from discrete tomography

Revue Internationale avec comité de lecture : Journal J. of Graph Algorithms and Applications, vol. 13(2), pp. 99-118, 2009
Résumé: 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 speci ed 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).

Equipe: oc
Collaboration: LAMSADE


@article {
title="{Degree-constrained edge partitioning in graphs arising from discrete tomography}",
author="C. Bentz and M.-C. Costa and C. Picouleau and B. Ries and D. de Werra",
journal="J. of Graph Algorithms and Applications",