Dans cette th`ese, nous proposons l'´etude d'un nouveau syst`eme de trafic a´erien, caract´eris´e par un tr`es haut degr´e d'organisation. Dans ce syst`eme, les avions sont assujettis `a suivre des points mobiles fictifs durant leur trajet. Ces points mobiles sont organis´es et s´equenc´es de fa¸con `a ´eviter les conflits entre avions, notamment lorsque ces derniers convergent vers une mˆeme intersection. Cette th`ese propose la mod´elisation d'un probl`eme sous-jacent `a ce paradigme. Ce probl`eme peut ˆetre vu comme la recherche d'un stable dans un graphe infini sous certaines contraintes. Apr`es une ´etude th´eorique de ce probl`eme, nous proposons une heuristique de r´esolution, amenant `a pr´esenter un syst`eme global de trafic a´erien, puis nous exposons des r´esultats num´eriques.

Ce document pr esente les travaux que j'ai r ealis es depuis ma th ese de doctorat. Outre la pr esentation de mes contributions, j'ai essay e de pr esenter des survols des domaines dans lesquels mes travaux s'inscrivent et d'indiquer les principales questions qui s'y posent. Mes travaux visent a r epondre aux nouveaux challenges algorithmiques que posent la croissance des r eseaux de telecommunications actuels ainsi que l'augmentation des donnees et du trafi c qui y circulent. Un moyen de faire face a la taille de ces probl emes est de s'aider de la structure particuliere des r eseaux. Pour cela, je m'attache a d e nir de nouvelles caract erisations des propri et es structurelles des graphes pour les calculer et les utiliser effi cacement a des fins algorithmiques. Autant que possible, je propose des algorithmes distribu es qui ne reposent que sur une connaissance locale/partielle des r eseaux. En particulier, j' etudie les jeux de poursuite - traitant de la capture d'une entit e mobile par une equipe d'autres agents - qui off rent un point de vue int eressant sur de nombreuses propri et es de graphes et, notamment, des d ecompositions de graphes. L'approche de ces jeux d'un point de vue agents mobiles permet aussi l' etude de mod eles de calcul distribu e. Le chapitre 1 est d edi e a l' etude de plusieurs variantes des jeux de gendarmes et voleur. Le chapitre 2 traite des decompositions de graphes et de leur relation avec les problemes d'encerclement dans les graphes. Le chapitre 3 se concentre sur les probl emes d'encerclement dans des contextes a la fois centralis e et distribu e. Finalement, le chapitre 4 traite de probl emes de routage dans diff erents contextes, ainsi que de mod eles de calcul distribu e.