Français Anglais
Accueil Annuaire Plan du site
Home > Groups > Research groups > Graph Theory and Combinatorial Optimization (GraphComb)
Groups
Graph Theory and Combinatorial Optimization (GraphComb)


Page no more maintained

as of 30 September 2013
please refer to the new team
GALaC


The goal of the "Graph Theory and Combinatorial Optimization" team (GraphComb) is to carry out researches in graph theory and combinatorial optimization, and to apply some of these researches to the study of real-life problems (network problems, resource allocation, etc.). The main three research themes of the team are:


  • Graph theory

  • Deterministic combinatorial optimization

  • Stochastic combinatorial optimization



Graph theory



The team researchers in the graph theory theme are interested in recent advances in the resolution of classical problems. A lot of these problems share the following common question: given one particular structure, does a given graph contain it? How to detect it, or even construct it, and, if possible, how to estimate how many times a structure of this type is contained in the graph? And how to find a structure similar, in some sense, to this one?

We also try to estimate, using several distinct techniques (which can be combinatorial, algebraic, algorithmic, etc.), the values of some parameters of the graph, which are related to some of its properties, and to study the links between these parameters.

Actually, these two points of view, the study of graph structures and the study of graph parameters, often provide complementary views on the same problem. For instance, determining whether a graph is hamiltonian or what the value of its circumference is needs to use the same kind of techniques. In both cases, we sometimes have to consider classes of graphs where the values of some parameters are more easily estimated, or where some structures are more easily detected.

The structures and parameters of interest depend on the applications one has to consider, since graphs can be used in very different and numerous ways. The number of different subjects studied by the team do not allow an exhaustive description of all of them: we only provide a list of four research topics in this theme, which are the most important ones. As further examples of our fields of research, we can mention the numerous researches led by the team concerning particular classes of graphs, or concerning specific parameters such as various coloring parameters, distance, toughness, etc.


  • Cycles in undirected and directed graphs

  • Decompositions and partitions

  • Algebraic aspects

  • Domination and related concepts



Deterministic combinatorial optimization


Some researchers of the team are also interested in methods and algorithms for solving combinatorial problems. These problems can be graph theoretic problems (such as maximum cut, partitioning or multiflows), or classical combinatorial optimization problems (such as quadratic assignment problems, knapsack problems, etc.), for which we design either new relaxations, especially semi-definite positive relaxations, or efficient algorithms. In this research theme, we are also interested in dealing with uncertainty via robust optimization.

The main research topics in this theme are:

  • Semi-definite positive relaxations

  • Robust optimization

  • Approximation algorithms



Stochastic combinatorial optimization


We are also interested in dealing with uncertainty via methods and algorithms for solving stochastic combinatorial optimization problems, where a subset of parameters is modelled by random variables. We work on methods for solving two- or multi-stage stochastic problems with recourse, and we also try to deal with probabilistic constraints for modelling the notion of risk.

The main research topics in this theme are:

  • Methods and algorithms for solving bi-level stochastic problems

  • Modelling the risk by considering probabilistic constraints


Group Members
  Group leader
    

Research activities
  Graph Theory
  Combinatorial optimization

Recent Ph.D. dissertations & faculty habilitations
  Optimisation stochastique biniveau
  Stochastic Optimization Problems with Knapsack Constraint
  Optimizing spectral efficiency on multiuser wireless networks

Seminars
A combinatorial approach to colourful simplicial depth
Antoine Deza
17 October 2013 14h00


Labeling schemes for bounded degree graphs
Noy Rotbart
20 September 2013 14h00


A queueing model for last mile delivery service with noncooperative customers
Dominique Quadri
5 April 2013 10h30


A Mathematical Programming Approach for Solving the General Art Gallery Problem
Mahdi Moeini
15 March 2013 10h30


Marches al'eatoires sur les graphes; Random walks on graphs
Charles Delorme
15 February 2013 10h30


Independent dominating sets in graphs by the semi-random method
Ararat Harutyunyan
8 February 2013 10h30


Algorithmes d'approximation à mémoire limitée pour le traitement de grands graphes
Romain CAMPIGOTTO
1 February 2013 10h30


La version graphe de la conjecture de Frankl
Henning Bruhn-Fujimoto
25 January 2013 00h00


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


Interdependencies of domination parameters in hereditary graph classes
Oliver Schaudt
7 December 2012 10h30


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


A SP approach for decision-dependent uncertainty in production planning under non-compliance risk
Alwin Haensel
5 October 2012 10h30


Implicit degrees and Hamiltonian graph theory
Hao Li
21 September 2012 10h30


Identifying codes in graphs of given maximum degree
Florent FOUCAUD
25 May 2012 10h30


Finding good decompositions for dynamic programming on dense graphs
Jan Arne Telle
2 December 2011 10h30


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


Towards Quantum Perfect Graph Theory
Hiroshi Imai
12 September 2011 10h30


Optimisation des réseaux à composantes unicycliques : approche polyédrale
Makhlouf HADJI
8 April 2011 10h00


Comparaison et évaluation en moyenne d'algorithmes d'approximation pour le problème du vertex cover
François DELBOT
1 April 2011 10h00


Méthodes d'approximation en complémentarité : applications en tomographie discrète et en parcimonie sous contraintes linéaires
Mounir HADDOU
4 March 2011 10h30


Supply-function equilibria in pay-as-bid electricity auctions
Andy PHILPOTT
11 February 2011 14h00


Décompositions induites de graphes
Adrian BONDY
10 December 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
5 November 2010 10h30


Un petit problème de dénombrement
Charles DELORME
1 October 2010 10h30


MIP models and exact solution approaches for the discrete lot-sizing and scheduling problem
Céline GICQUEL
9 April 2010 10h30


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


Résolution du problème de ramassage et livraison préemptif
Mathieu LACROIX
12 March 2010 10h30


Comparaison de structures d'ARN, comparaison d'arbres, comparaison de graphes
Alain DENISE
19 February 2010 10h30


Cyclic partitions of complete uniform hypergraphs
A. Pawel WOJDA
5 February 2010 10h30


Graphes à défaut ou excès cyclique
Charles DELORME
22 January 2010 10h30


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


On graph coloring problems with local constraints
Flavia BONOMO
11 December 2009 10h30


An SDP approach to the linear ordering problem
Franz RENDL
27 November 2009 10h30


Game Theoretic Models for Competition in Public Transit Services
Janny LEUNG
25 November 2009 10h30


On two-stage stochastic knapsack problems
Stefanie KOSUCH
13 November 2009 10h30


Stochastic Quadratic Knapsack with Recourse
Rafaël LOPEZ
6 November 2009 10h30


A survey on the prism hamiltonian problems
Haiyan KANG
23 October 2009 10h30


Stochastic Knapsack Problem with Continuous Distributions
Marc LETOURNEL
9 October 2009 10h30


1,2 conjecture and some related problems
Mariusz WOZNIAK
2 October 2009 10h30


Triplets de Steiner
Charles DELORME
25 September 2009 10h30


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


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


Cycles hamiltoniens et couplages
Gancarzewicz Grzegorz
27 March 2009 10h30


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


Arbres de connexion en ligne : évaluation au pire cas et en moyenne
Nicolas THIBAULT
6 March 2009 11h00


On hamiltonian cycles in star graphs
Roman CADA
6 March 2009 10h15


Racines carrées de graphes
David AUGER
20 February 2009 10h30


Minimum blockers and transversals in graphs
Cédric BENTZ
13 February 2009 10h30


Nombre d'arêtes communes à deux graphes, spectre et spectre singulier
Charles DELORME
6 February 2009 10h30


Nordhaus-Gaddum inequalities for the game domination number
Odile FAVARON
30 January 2009 10h30


Distance maximum entre ordres de Slater et ordres de Copeland de tournois
Olivier HUDRY
23 January 2009 10h30


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


Résolution exacte du problème d'affectation quadratique à trois dimensions
François GALEA
9 January 2009 10h30


Recherche de solutions de compromis dans des problèmes de graphes multicritères
Lucie GALAND
12 December 2008 10h30


Timetable Synchronization for Rail Mass Transit
Janny M.Y. LEUNG
5 December 2008 10h30


Long cycles and cyclability in graphs
Hao LI
14 November 2008 10h30


Approches Polyédrales et Conception de Réseaux
Ridha MAHJOUB
7 November 2008 10h30


Portaits de famille
Charles DELORME
3 October 2008 10h30


Matching forcing number in fullerene graphs
Heping Zhang
30 May 2008 16h05


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


Coloring Vertices and Edges of a Path by Nonempty Subsets of a Set
Ervin Gyori
30 May 2008 14h15


Cycles et Facteurs dans les Graphes
Shan Zhou
30 May 2008 10h30


Partition des sommets d'un graphe en stables et cliques
Pascal Ochem
16 May 2008 10h30


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


Some New Results on Cycles and Paths
Shan ZHOU
21 March 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
14 March 2008 10h30


Codes identifiants dans les graphes
David AUGER
22 February 2008 10h30


Représentations d'arbres plans
Charles DELORME
25 January 2008 10h30


Size conditions for long cycles in graphs and digraphs
Lech ADAMUS
11 January 2008 10h15


Résultats majeurs
Software & patents