Abstract FR:

Ce travail concerne les problemes de complexite dans les graphes aretes-colores. Plus particulierement, nous nous interessons aux aspects algorithmiques de la question, tant du point de vue parallele que du point de vue sequentiel. Nous traitons principalement des problemes de recherche de certains cycles ou chaines alternes dans des graphes aretes-colores: circuit hamiltoniens, cycles euleriens, cycles passant par un nombre donnees de sommets, etc nous donnons aussi quelques preuves de np-completude dans les graphes aretes-colores