Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$41,000.00
Théorie des graphes : algorithmique, aspects structurels, théorie extrémale et applications
EF 2017-18
Résumé
Les projets de recherche que je compte raliser et encadrer durant ces 5 prochaines annes sont multiples et complmentaires. Ils vont de la recherche fondamentale en thorie des graphes (aspects structurels, thorie extrmale, etc.) au dveloppement dalgorithmes efficaces pour la rsolution de problmes rels quon peut modliser laide des graphes. Ces projets sont regroups en 3 thmes principaux. Le premier thme est l'tude d'extensions de problmes classiques de colorations de graphes. Par exemple, au lieu dinterdire que les extrmits d'une arte aient la mme couleur, on peut imposer une limite sur le nombre de violations de cette contrainte; ceci donne lieu des colorations impropres qui apparaissent naturellement en tlcommunication. Comme autre exemple, on peut citer la coloration de graphes mixtes dans lesquels des contraintes de prcdence forcent certains sommets avoir une couleur (reprsente par un nombre) plus petite que dautres; ces colorations permettent de modliser des problmes dordonnancement de type job-shop. Le deuxime thme est l'tude du problme de l'arbre de Steiner avec capacit, qui est un modle naturel lors de la conception de rseaux de collecte dnergie olienne ou de distribution dlectricit. tant donn un graphe pondr dont les artes ont des capacits, et un sous-ensemble S de sommets contenant une racine r, le problme rsoudre est de dterminer un arbre induit, enracin en r, contenant tous les sommets de S, qui soit de poids minimum (problme de Steiner classique), tout en satisfaisant la contrainte de capacit suivante : pour chaque arte e, le nombre de chanes qui contiennent e et qui relient r aux sommets de S ne doit pas excder la capacit de e. Le troisime thme consiste borner les invariants dun graphe ou les comparer entre eux (plus grande ou petite diffrence de valeur) et dterminer les graphes extrmaux qui atteignent ces bornes. Un intrt particulier sera port sur les invariants tels que la proximit, lloignement ou lexcentricit pour lesquels de nombreuses bornes restent dterminer et qui sont essentiels une bonne comprhension de la structure dun rseau donn. Les modles standards en thorie des graphes sont souvent trop simples pour traiter les problmes rencontrs en pratique. Ce nest quen les tendant et en les adaptant quon peut russir gnrer des solutions satisfaisantes. Les projets susmentionns ont pour but de produire des modles et des techniques de rsolution adapts un grand ventail de problmes auxquels les entreprises sont quotidiennement confrontes. Lincidence principale de ces recherches sera de procurer des outils efficaces aux dcideurs des principaux secteurs industriels qubcois et d'ailleurs. Aussi, les tudiants impliqus dans ces travaux seront confronts des problmes industriels rels, ce qui leur ouvrira d'excellentes perspectives d'emploi la fin de leurs tudes.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2017-05688
Name nom
Hertz, Alain
Department département
Mathématiques et génie industriel - Mathématiques et génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2017
Award amount
41000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
1
Nb partie
5
Application title
Théorie des graphes : algorithmique, aspects structurels, théorie extrémale et applications
Keyword
NSERC
Application summary
Les projets de recherche que je compte raliser et encadrer durant ces 5 prochaines annes sont multiples et complmentaires. Ils vont de la recherche fondamentale en thorie des graphes (aspects structurels, thorie extrmale, etc.) au dveloppement dalgorithmes efficaces pour la rsolution de problmes rels quon peut modliser laide des graphes. Ces projets sont regroups en 3 thmes principaux. Le premier thme est l'tude d'extensions de problmes classiques de colorations de graphes. Par exemple, au lieu dinterdire que les extrmits d'une arte aient la mme couleur, on peut imposer une limite sur le nombre de violations de cette contrainte; ceci donne lieu des colorations impropres qui apparaissent naturellement en tlcommunication. Comme autre exemple, on peut citer la coloration de graphes mixtes dans lesquels des contraintes de prcdence forcent certains sommets avoir une couleur (reprsente par un nombre) plus petite que dautres; ces colorations permettent de modliser des problmes dordonnancement de type job-shop. Le deuxime thme est l'tude du problme de l'arbre de Steiner avec capacit, qui est un modle naturel lors de la conception de rseaux de collecte dnergie olienne ou de distribution dlectricit. tant donn un graphe pondr dont les artes ont des capacits, et un sous-ensemble S de sommets contenant une racine r, le problme rsoudre est de dterminer un arbre induit, enracin en r, contenant tous les sommets de S, qui soit de poids minimum (problme de Steiner classique), tout en satisfaisant la contrainte de capacit suivante : pour chaque arte e, le nombre de chanes qui contiennent e et qui relient r aux sommets de S ne doit pas excder la capacit de e. Le troisime thme consiste borner les invariants dun graphe ou les comparer entre eux (plus grande ou petite diffrence de valeur) et dterminer les graphes extrmaux qui atteignent ces bornes. Un intrt particulier sera port sur les invariants tels que la proximit, lloignement ou lexcentricit pour lesquels de nombreuses bornes restent dterminer et qui sont essentiels une bonne comprhension de la structure dun rseau donn. Les modles standards en thorie des graphes sont souvent trop simples pour traiter les problmes rencontrs en pratique. Ce nest quen les tendant et en les adaptant quon peut russir gnrer des solutions satisfaisantes. Les projets susmentionns ont pour but de produire des modles et des techniques de rsolution adapts un grand ventail de problmes auxquels les entreprises sont quotidiennement confrontes. Lincidence principale de ces recherches sera de procurer des outils efficaces aux dcideurs des principaux secteurs industriels qubcois et d'ailleurs. Aussi, les tudiants impliqus dans ces travaux seront confronts des problmes industriels rels, ce qui leur ouvrira d'excellentes perspectives d'emploi la fin de leurs tudes.