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.
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