Degreeconstrained edge partitioning in graphs arising from discrete tomography

Bentz, Cédric
Université ParisSud, France

Costa, MarieChristine
CNAM, Paris

Picouleau, Christophe
CNAM, Paris

Ries, Bernard
EPFL, Switzerland

de Werra, Dominique
EPFL, Switzerland
Show more…
Published in:
 Journal of Graph Algorithms and Applications.  2009, vol. 13, no. 2, p. 99118
English
Starting from the basic problem of reconstructing a 2dimensional 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, 2factor, etc.). We also study special cases corresponding to the search of 2 edgedisjoint 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


Classification

Computer science and technology

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/307829
Statistics
Document views: 40
File downloads:
 discretetomography.pdf: 46