CE48 - Fondements du numérique: informatique, automatique, traitement du signal

DAGs and Digraph Decompositions – DAGDigDec

Submission summary

The study of directed graphs (or digraphs) is as old, although not as comprehensive, as that of undirected graphs. The last several decades have seen a great appreciation of directed graphs by researchers and an increase in the number of papers in this important area. A central notion appearing in the study of digraphs is that of a Directed Acyclic Graph (also known as DAG), a digraph without directed cycles. It is hard to overstate the role that DAGs play in computer science and discrete mathematics. Their applications in telecommunications, sorting, scheduling, data compression, and data processing are ubiquitous. Curiously enough, compared to their practical importance, fundamental knowledge and understanding of DAGs is not as broad or deep as one would like. The main goal of this project is to study how DAGs affect the structure and properties of digraphs which contain them.

Project coordinator

Monsieur Ararat Harutyunyan (Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.


LAMSADE Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision

Help of the ANR 176,736 euros
Beginning and duration of the scientific project: September 2021 - 48 Months

Useful links

Explorez notre base de projets financés



ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter