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

Page no more maintained

as of 30 September 2013
please refer to the new team

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

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
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
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
4 March 2011 10h30

Supply-function equilibria in pay-as-bid electricity auctions
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
5 November 2010 10h30

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

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

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

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

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

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

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

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

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

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

Game Theoretic Models for Competition in Public Transit Services
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
9 October 2009 10h30

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

Triplets de Steiner
25 September 2009 10h30

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

Treewidth and logical definability of graph products - Part one
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
13 March 2009 10h30

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

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

Racines carrées de graphes
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
6 February 2009 10h30

Nordhaus-Gaddum inequalities for the game domination number
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
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
7 November 2008 10h30

Portaits de famille
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
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
14 March 2008 10h30

Codes identifiants dans les graphes
22 February 2008 10h30

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

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

Résultats majeurs
Software & patents