I am a post doctoral fellow at LIP6 laboratory (University of Paris 6) in the Complex Networks group.
E-mail: christophe tod crespelle wat lip6 odt fr (replace the three-letter words with . @ .)
Phone: (0/+33) 1 44 27 88 68
Address:
LIP6
Bureau 537
104, Avenue du Président Kennedy
75016 Paris
My main topics are Algorithms and Graph Theory. I am particularly interested in algorithms for geometric graph classes, such as permutation graphs, interval graphs and their variants (circle graphs, circular-arc graphs). When dealing with such classes, the question of graph representation is crucial. The representation coming from the geometric definition allows to efficiently solve many problems. But for some purposes, such as dynamic maintain or optimisation, better representations are needed. In this context, general graph decompositions (for example modular decomposition, split decomposition, clique separator decomposition, Tutte decomposition) can be of great help.
I am also involved in applications of graph theoretic concepts and algorithms in the context of complex networks. The term of complex networks refers to graphs encountered in various contexts such as communications, industry, social sciences and physics. In the late 90's, it was discovered that those graphs coming from very different practical situations share some common properties (e.g. low diameter, power-law degree distribution, high local density). These properties, which are not all satisfied by random graphs, are non trivial and it is interesting to take advantage of them for automatised treatment. In this context, I am particularly interested in introducing graph-representation-based properties in order to analyse these networks (i.e. find out their structures), modelise them (e.g. for generation purposes) and devise algorithms that efficiently solve problems pertinent to their practical contexts. The difficulty with using graph theoretic properties to deal with these objects is that, by definition, they do not strictly verify any mathematical property : their properties are statistical and approximate. Nevertheless, these graphs have strong structures conferred by their original context. Therefore, the challenge is to soften classic graph theoretic notions in order to find out their structures and take benefit of them for computing purposes.
In many contexts, the graphs considered are submitted to changes along the time. Then the question of dynamically maintaining these structures arise. It is particularly crucial when the changes occurs at a high frequency or when the amount of data involved is large, many systems having both characteristics. Then, it is accurate to design representations allowing to deal efficiently with this dynamics. An other approach of great interest is to take advantage of the structure of the modifications itself. Indeed, the changes occurring on the graphs are constrained by the context and must therefore have their own structure reflecting it. No doubt that considering this structure would lead to great improvement of our capacity to deal with the dynamics of complex networks.