Français Anglais
Accueil Annuaire Plan du site
Accueil > Equipes > Toutes les équipes > Théorie des Graphes et Optimisation Combinatoire (GraphComb)
Equipes
Théorie des Graphes et Optimisation Combinatoire (GraphComb)


Page non-maintenue

depuis le 30 septembre 2013
se référer à la nouvelle équipe
GALaC ou
ROCS


L'équipe "Théorie des Graphes et Optimisation Combinatoire" (GraphComb) a pour objectif le développement de recherches en théorie des graphes et en optimisation combinatoire déterministe et stochastique, et l'application d'une partie de ces recherches à la résolution de problèmes pratiques (réseaux, planification, allocation de ressources). L'équipe distingue ainsi trois axes principaux de recherche :


  • Théorie des graphes

  • Optimisation combinatoire déterministe

  • Optimisation combinatoire stochastique



Théorie des graphes



En ce qui concerne la théorie des graphes l'équipe s'intéresse à des problèmes classiques sous leurs développements les plus récents. Une description commune à beaucoup de ces problèmes est la suivante : étant donnée telle structure, un graphe la contient-il ? Comment la détecter, voire la construire, et éventuellement estimer combien de fois elle est présente ? Comment trouver dans le graphe une structure voisine ?

On cherche aussi à évaluer grâce à diverses techniques (combinatoires, algébriques, algorithmiques, etc...) des paramètres liés à certaines propriétés du graphe et à étudier les relations et les interactions existant entre les divers paramètres.

En fait ces deux points de vue, étude de structures et de paramètres, induisent souvent deux approches complémentaires d'une même question. Par exemple, rechercher si un graphe est hamiltonien ou quelle est la valeur de sa circonférence relève de la même idée et des mêmes techniques. Dans les deux cas, nous sommes parfois conduits à mettre en lumière des classes de graphes dans lesquelles certains paramètres sont plus aisément évalués, ou certaines structures plus facilement détectées.

Les structures et paramètres intéressants varient selon les applications envisagées car les graphes présentent une grande souplesse d'utilisation. Les sujets d'étude abordés étant trop nombreux pour pouvoir être tous décrits (voir la bibliographie des participants), nous citerons seulement quatre sous-axes de recherche importants pour notre groupe. Comme exemples d'autres domaines de travail, on peut citer les nombreuses études menées dans des classes de graphes spécifiques et celles portant sur des paramètres de coloration, distance ou toughness ou sur l'existence de certains facteurs.


  • Cycles dans les graphes et graphes orientés

  • Décompositions et placements

  • Aspects algébriques

  • Concepts issus de la domination



Optimisation combinatoire déterministe



Une partie de l’équipe s’intéresse aux méthodes et algorithmes de résolution de problèmes combinatoires. Il s’agit soit de problèmes de graphes (coupe maximale, partitionnement, multiflots), soit de problèmes d’optimisation combinatoire classiques (affectation quadratique, problème du sac-à-dos), pour lesquels l’équipe propose soit de nouvelles relaxations (plus particulièrement des relaxations semi-définies positives), soit des algorithmes efficaces. Dans cette thématique, l’équipe s’intéresse à la prise en compte de l’incertitude à travers l’optimisation robuste.

Les principaux sous-axes de recherche de l'équipe sont :


  • Relaxation semi-définie positive

  • Optimisation robuste

  • Algorithmes d’approximation



Optimisation combinatoire stochastique



Dans le prolongement de l’optimisation robuste et de la prise en compte de l’incertitude, nous nous intéressons aux méthodes et algorithmes de résolution de problèmes d’optimisation combinatoire stochastique où un sous-ensemble de paramètres est représenté par des variables aléatoires. Nos travaux portent sur les méthodes de résolution de problèmes stochastiques à deux (ou plusieurs) niveaux avec recours ainsi que sur la prise en compte de contraintes probabilistes pour la modélisation du risque.

Les principaux sous-axes de recherche de l’équipe sont :


  • Méthodes et algorithmes de résolution de problèmes stochastiques à deux niveaux

  • Modélisation du risque et prise en compte de contraintes probabilistes


Composition de l'équipe
  Responsable
    LISSER Abdel

Activités de recherche
  Théorie des graphes
  Optimisation combinatoire

Thèses et habilitabions récentes
  Optimisation stochastique biniveau
  Stochastic Optimization Problems with Knapsack Constraint
  Optimizing spectral efficiency on multiuser wireless networks

Séminaires
A combinatorial approach to colourful simplicial depth
Antoine Deza
Jeu. 17 octobre 2013 - 14h00


Labeling schemes for bounded degree graphs
Noy Rotbart
Ven. 20 septembre 2013 - 14h00


A queueing model for last mile delivery service with noncooperative customers
Dominique Quadri
Ven. 05 avril 2013 - 10h30


A Mathematical Programming Approach for Solving the General Art Gallery Problem
Mahdi Moeini
Ven. 15 mars 2013 - 10h30


Marches al'eatoires sur les graphes; Random walks on graphs
Charles Delorme
Ven. 15 février 2013 - 10h30


Independent dominating sets in graphs by the semi-random method
Ararat Harutyunyan
Ven. 08 février 2013 - 10h30


Algorithmes d'approximation à mémoire limitée pour le traitement de grands graphes
Romain CAMPIGOTTO
Ven. 01 février 2013 - 10h30


La version graphe de la conjecture de Frankl
Henning Bruhn-Fujimoto
Ven. 25 janvier 2013 - 00h00


Optimisation combinatoire dans les réseaux et dans le cloud : approche polyèdrale vs heuristiques
Makhlouf Hadji
Ven. 18 janvier 2013 - 09h30


Interdependencies of domination parameters in hereditary graph classes
Oliver Schaudt
Ven. 07 décembre 2012 - 10h30


Bilevel stochastic optimization problems with applications to telecommunications
Alexei A. Gaivoronski
Ven. 16 novembre 2012 - 10h30


A SP approach for decision-dependent uncertainty in production planning under non-compliance risk
Alwin Haensel
Ven. 05 octobre 2012 - 10h30


Implicit degrees and Hamiltonian graph theory
Hao Li
Ven. 21 septembre 2012 - 10h30


Identifying codes in graphs of given maximum degree
Florent FOUCAUD
Ven. 25 mai 2012 - 10h30


Finding good decompositions for dynamic programming on dense graphs
Jan Arne Telle
Ven. 02 décembre 2011 - 10h30


An Ant Colony Optimization Algorithm for the Two-Stage Knapsack Problem
Stefanie KOSUCH
Ven. 28 octobre 2011 - 10h30


Towards Quantum Perfect Graph Theory
Hiroshi Imai
Lun. 12 septembre 2011 - 10h30


Optimisation des réseaux à composantes unicycliques : approche polyédrale
Makhlouf HADJI
Ven. 08 avril 2011 - 10h00


Comparaison et évaluation en moyenne d'algorithmes d'approximation pour le problème du vertex cover
François DELBOT
Ven. 01 avril 2011 - 10h00


Méthodes d'approximation en complémentarité : applications en tomographie discrète et en parcimonie sous contraintes linéaires
Mounir HADDOU
Ven. 04 mars 2011 - 10h30


Supply-function equilibria in pay-as-bid electricity auctions
Andy PHILPOTT
Ven. 11 février 2011 - 14h00


Décompositions induites de graphes
Adrian BONDY
Ven. 10 décembre 2010 - 10h30


Le nombre des arbres de longueur minimale joignant dans la grille triangulaire les sommets d'un hexagone de 2 en 2
Charles DELORME
Ven. 05 novembre 2010 - 10h30


Un petit problème de dénombrement
Charles DELORME
Ven. 01 octobre 2010 - 10h30


MIP models and exact solution approaches for the discrete lot-sizing and scheduling problem
Céline GICQUEL
Ven. 09 avril 2010 - 10h30


Sur une suite universelle d'entiers génératrice de figures de Steinhaus équilibrées
Jonathan CHAPPELON
Ven. 26 mars 2010 - 10h30


Résolution du problème de ramassage et livraison préemptif
Mathieu LACROIX
Ven. 12 mars 2010 - 10h30


Comparaison de structures d'ARN, comparaison d'arbres, comparaison de graphes
Alain DENISE
Ven. 19 février 2010 - 10h30


Cyclic partitions of complete uniform hypergraphs
A. Pawel WOJDA
Ven. 05 février 2010 - 10h30


Graphes à défaut ou excès cyclique
Charles DELORME
Ven. 22 janvier 2010 - 10h30


Treewidth and logical definability of graph products - Part three
Selma DJELLOUL
Ven. 15 janvier 2010 - 10h30


On graph coloring problems with local constraints
Flavia BONOMO
Ven. 11 décembre 2009 - 10h30


An SDP approach to the linear ordering problem
Franz RENDL
Ven. 27 novembre 2009 - 10h30


Game Theoretic Models for Competition in Public Transit Services
Janny LEUNG
Mer. 25 novembre 2009 - 10h30


On two-stage stochastic knapsack problems
Stefanie KOSUCH
Ven. 13 novembre 2009 - 10h30


Stochastic Quadratic Knapsack with Recourse
Rafaël LOPEZ
Ven. 06 novembre 2009 - 10h30


A survey on the prism hamiltonian problems
Haiyan KANG
Ven. 23 octobre 2009 - 10h30


Stochastic Knapsack Problem with Continuous Distributions
Marc LETOURNEL
Ven. 09 octobre 2009 - 10h30


1,2 conjecture and some related problems
Mariusz WOZNIAK
Ven. 02 octobre 2009 - 10h30


Triplets de Steiner
Charles DELORME
Ven. 25 septembre 2009 - 10h30


Treewidth and logical definability of graph products - Part two
Selma DJELLOUL
Ven. 19 juin 2009 - 10h30


Treewidth and logical definability of graph products - Part one
Selma DJELLOUL
Ven. 12 juin 2009 - 10h30


Cycles hamiltoniens et couplages
Gancarzewicz Grzegorz
Ven. 27 mars 2009 - 10h30


La taille maximale de graphes planaires avec le degré et diamètre fixés
Serge TISHCENKO
Ven. 13 mars 2009 - 10h30


Arbres de connexion en ligne : évaluation au pire cas et en moyenne
Nicolas THIBAULT
Ven. 06 mars 2009 - 11h00


On hamiltonian cycles in star graphs
Roman CADA
Ven. 06 mars 2009 - 10h15


Racines carrées de graphes
David AUGER
Ven. 20 février 2009 - 10h30


Minimum blockers and transversals in graphs
Cédric BENTZ
Ven. 13 février 2009 - 10h30


Nombre d'arêtes communes à deux graphes, spectre et spectre singulier
Charles DELORME
Ven. 06 février 2009 - 10h30


Nordhaus-Gaddum inequalities for the game domination number
Odile FAVARON
Ven. 30 janvier 2009 - 10h30


Distance maximum entre ordres de Slater et ordres de Copeland de tournois
Olivier HUDRY
Ven. 23 janvier 2009 - 10h30


Programmation Semidéfinie pour l'optimisation dans les graphes : approches classiques et variantes récentes
Frédéric ROUPIN
Ven. 16 janvier 2009 - 10h30


Résolution exacte du problème d'affectation quadratique à trois dimensions
François GALEA
Ven. 09 janvier 2009 - 10h30


Recherche de solutions de compromis dans des problèmes de graphes multicritères
Lucie GALAND
Ven. 12 décembre 2008 - 10h30


Timetable Synchronization for Rail Mass Transit
Janny M.Y. LEUNG
Ven. 05 décembre 2008 - 10h30


Long cycles and cyclability in graphs
Hao LI
Ven. 14 novembre 2008 - 10h30


Approches Polyédrales et Conception de Réseaux
Ridha MAHJOUB
Ven. 07 novembre 2008 - 10h30


Portaits de famille
Charles DELORME
Ven. 03 octobre 2008 - 10h30


Matching forcing number in fullerene graphs
Heping Zhang
Ven. 30 mai 2008 - 16h05


Upper bounds on the number of components of 2-factors in claw-free graphs
Hajo Broersma
Ven. 30 mai 2008 - 15h10


Coloring Vertices and Edges of a Path by Nonempty Subsets of a Set
Ervin Gyori
Ven. 30 mai 2008 - 14h15


Cycles et Facteurs dans les Graphes
Shan Zhou
Ven. 30 mai 2008 - 10h30


Partition des sommets d'un graphe en stables et cliques
Pascal Ochem
Ven. 16 mai 2008 - 10h30


Problème du sac-à-dos stochastique quadratique
Rafaël Lopez
Ven. 18 avril 2008 - 10h30


Some New Results on Cycles and Paths
Shan ZHOU
Ven. 21 mars 2008 - 10h30


Un théorème de structure pour les graphes ne contenant pas de cycle avec une unique corde comme sous-graphe induit
Nicolas TROTIGNON
Ven. 14 mars 2008 - 10h30


Codes identifiants dans les graphes
David AUGER
Ven. 22 février 2008 - 10h30


Représentations d'arbres plans
Charles DELORME
Ven. 25 janvier 2008 - 10h30


Size conditions for long cycles in graphs and digraphs
Lech ADAMUS
Ven. 11 janvier 2008 - 10h15


Résultats majeurs
Logiciels et brevets