Rachid Saad
Alternating path problems in edge-colored graphs

This talk is a review of my own work with several other co-authors (from Paris XI) on the subject of alternating paths. Given an edge-colored graph, the question we ask ourselves, in broad terms, is this: are there any sufficient conditions guranteeing the existence of alternating configurations such as: a flow of alternating paths linking a vertex to other fixed vertices, hamiltonian alternating paths...etc. Preoccupation with computational complexity issues are central to the main focus of this work.

Open problems will be presented.