**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 leader