DIGRAPHS (Directed graphs) is a research project funded by Agence Nationale de la Recherche (code ANR-???). It gathers reserchers from three laboratories: LIRMM (Equipe AlGCo), LIP (Equipe MC2, ENS Lyon), et l’I3S (Equipe COATI, Sophia Antipolis). Il a débuté en janvier 2014
Directed graphs (digraphs for short) are naturally used to model many real-world problems. For example, many graphs modelling networks are by essence directed (web graph, twitter graph, . . . ). To address those problems, we need to have a better understanding of structural and algorithmic aspects of digraphs. However, for various reasons, digraph theory is a lot less developed than (undirected) graph theory. One of the reasons is that, very often, a problem on graphs corresponds to a particular case (in general for symmetric digraphs) of an analogue problem on digraphs. Therefore digraph problems are intrinsically more difficult than graph problems.
The objectives of the project is to make some advances on digraph theory in order to get a better understanding of important aspects of digraphs and to have more insight on the differences and the similarities between graphs and digraphs. We will mainly focus on digraph partition problems.
On the second hand, we will consider many results on graphs, find their (possibly many) formulations in terms of digraphs and see if and how they can be extended. Studying such extensions has been occasionally done, but the point here is to do it in a kind of systematic way.