Lifo - Laboratoire d'Informatique Fondamentale d'orléans INSA Centre Val de Loire Université d'Orléans Université d'Orléans

Lifo > GAMoC : Graphs, Algorithms and Models of Computation

 Site en Français



Contact

LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2

Email: contact.lifo
Tel: +33 (0)2 38 41 99 29
Fax: +33 (0)2 38 41 71 37



GAMoC : Graphs, Algorithms and Models of Computation

Full Professor

Assistant Professor

Post-Doc

ATER (Temporary Assistant Professor)

Doctoral Student


Research topics

  • Graph combinatorics and cubic graphs.

  • Exact algorithms for NP-hard problems.

  • Continuous computation models.

Graph combinatorics and cubic graphs

Cubic graphs appear in several important conjectures (TUTTE's 5-flow conjecture, the conjectures of FULKERSON and of FAN and RASPAUD) which are related to the famous 4-colors theorem. It is equivalent to show that every planar graph is four-colorable or that every planar cubic graph is 3 edge-colorable. From this point of view, the structure cubic graphs, planar or non-planar, is an important subject. We have studied linear partitions of cubic graphs (partitions of the edge set into two classes, such that each class induces a union of elementary paths) and normal partitions into trails (each vertex is the end vertex of a unique trail in the decomposition of the edge set); 3 edge-colorability is naturally related to these partitions.

We also study graph classes in which some configurations appear sparsely. We are particularly interested in configurations such that, by forbidding them, we obtain graph classes with strong structural properties. Based on decomposition methods, we adress algorithmic issues like the recognition and optimisation problems for these classes.

Exact algorithms for NP-hard problems

In the area of exact algorithms, we aim at computing optimal solutions for NP-hard optimization problems. Our algorithms will have exponential worst-case running time, but nevertheless our goal is to make them as efficient as possible. This is a very active research area in algorithms, for at least two good reasons. On the practical side, it is often important to give exact solutions to a given problem, rather than approximate ones; this is tipically the case in resource allocation problems with expensive ressources. Nowadays, exponential algorithms with moderate complexity can be run efficiently on powerfull computers, on inputs of "reasonable" size. On the theoretical side, let us quote Gödel's letter to von Newmann (1956): "It would be interesting to know [...] how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search". This question about the best possible algorithm for a given problem is at the very heart of complexity theory.

For effeciently solving NP-hard problems, we develop approches based on graph-decomposition techniques (e.g. related to the treewidth of the input graph). We have good expertize in using and extending very recent algorithmic techniques as measure and conquer for branching algorithms, iterative compression, subset convolution etc. We have contributed to a new technique for the design and analysis of exact algorithms, called branch and recharge.

Continuous computation models

Several models of computations propoposed during the last decade differ from the classical computation models and the Church-Turing thesis. These new models are based on computations with real numbers or on hypercomputing with infinite time Turing machines. We have introduced and studied a modeled called Abstract Geometrical Computation, a signal-based machine inspired by cellular automatas. The classical (discrete) signal is placed here into a different framework, where time and space are continuous. This model does not fit anymore into the classical recursivity theory, by the fact that dates and positions correspond now to real numbers. We have shown that our model can simulate the BSS model as well as Turing machines of the 2nd type (where real numbers are represented by a sequence of approximations). We currently study fractals, naturally generated by our model, which can be used to implement "procedures" and thus allow exponential speed-up.

We are also interested in self-assembly. The study of this model relies on discrete signals, thus it has a natural relationship with the Abstract Geometrical Computation model.

Future research directions of the Graph and Algorithms project

We will continue our work on cubic graphs as well on other combinatorial questions related to (H,k)-stable graphs and the Seidel switch.

We pursue our projects on exact algorithms and specific algorithmic and combinatorial techniques (graph decompositions and width parameters, meaure and conquer, branch and recharge).

Continuous computation models leave open a large number of research directions, e.g. the relationship between accumulation phenomena and the hyperarithmetic hierarchy, or the bridges between the continous signals machine and other computation models. We are also interested in constructions that can be automatically translated into cellular automata models, preserving some special properties.

We are also interested in the algorithmics of several types of networks, in particular in aspects related to the dynamics and the communication complexity in such networks, which require tools both from graph theory and celullar automata.

Collaborations and projects

We have stong ties with the University of Bergen (Norway), the AGH University of Krakow (Poland) and the University of Chile (Santiago, Chile). In particular, we have several international programmes (EGIDE, ECOS-Conicyt) supporting these collaborations, and we had several visits, in both directions, of PhD students and permanent researchers. We intend to continue and intensify the students exchanges, particularly through Erasmus programmes.

Organzation of conferences and workshops

Projects

  • ANR AGAPE: Exact and Fixed-Parameter Graph Algorithms (French National Research Agency, 2009-2013)
  • PEPS GraphIQ Projet Exploratoire Pluridisciplinaires supported by the INS2I (CNRs): Quantum computing and graph theory (GraphIQ, 2010-2011)
  • French-chilean programme ECOS-Concyt : Graph realization with contstraint degrees (2010-2012)
     
  • ANR STAL-DEC-OPT: Graph decomposition techniques for constraint-satisfaction programming (2005-2008)
  • French-norvegian programmes PHC EGIDE-Aurora on minimal separators and tree decompositions (2004-2006 and 2008-2009)
  • French-chilean programme ECOS-Conicyt : Tilings: flips and self-assembly (2005-2008)