Exploration des graphes arêtes-colorées : topologie, algorithmes, complexité et (non)-approximabilité
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
The graphs which edges are colored with c>1 colors, with c is a given integer, in other words c-edge-colored graphs, have a growing number of fields of applications particularly in molecular biology and VLSI. Their theoretical motivation is obvious sine they are a generalization of digraphs. In the present work, we explore these graphs to extract and study structures (i. E. Subgraphs) called properly-edge-colored which every pair of adjacent edges differ in color. We start this work by a part introducing the most notable results in the literature and cover the majority of questions treated in this topic since the sixties. In the second part, first we give characterizations of certain properly-edge-colored structures such as paths and cycles. After that, we were interested by the construction of polynomial algorithms, the study of complexity and approximability aspect of a variety of structures.
Abstract FR:
Les graphes dont les arêtes sont coloriées par c>1 couleurs, avec c un entier donné, autrement dit les graphes c-arêtes-colorées, connaissent un nombre grandissant de champs d’applications notamment en biologie moléculaire et en technologie intégrée à très grande échelle sans oublier leur intérêt théorique puisqu’ils sont une généralisation des graphes orientés. Dans cette thèse nous explorons ces graphes pour extraire et étudier les structures (i. E. , les sous-graphes) dites proprement-arêtes-coloriées c'est-à-dire dans lesquelles chaque paire d’arêtes adjacentes sont de couleurs distinctes. Tout d’abord, nous avons jugé nécessaire de réserver la première partie de la thèse à un état de l’art qui présente les travaux les plus importants et couvre la majorité des questions traitées dans ce domaine depuis les années soixante. En suite, dans une deuxième partie, nous avons commencé par donner des caractérisations de certaines structures proprement-arêtes-coloriées telles que les chaînes et les cycles, et puis nous nous sommes orientés vers la construction des algorithmes, l’étude de l’aspect de la complexité et l’approximabilité d’une variété de structures.