Degree-constrained edge partitioning in graphs arising from discrete tomography
- Bentz, Cédric Université Paris-Sud, France
- Costa, Marie-Christine CNAM, Paris
- Picouleau, Christophe CNAM, Paris
- Ries, Bernard EPFL, Switzerland
- de Werra, Dominique EPFL, Switzerland
-
2009
Published in:
- Journal of Graph Algorithms and Applications. - 2009, vol. 13, no. 2, p. 99-118
English
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).
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 326908
- DOI 10.7155/jgaa.00178
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307829
Statistics
Document views: 50
File downloads:
- discretetomography.pdf: 88