**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Directed acyclic graph

Summary

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to information science (citation networks) to computation (scheduling).
Directed acyclic graphs are sometimes instead called acyclic directed graphs or acyclic digraphs.
Definitions
A graph is formed by vertices and by edges connecting pairs of vertices, where the vertices can be any kind of object that is connected in pairs by edges.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people (5)

Related publications (65)

Loading

Loading

Loading

Related lectures (50)

Related units (4)

Related courses (25)

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, sorting and searching, and graph algorithms.

ME-427: Networked control systems

This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportunities offered by communication will be analyzed.

CS-550: Formal verification

We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to use formal verification tools and explain the theory and the practice behind them.

Big-Data streaming applications are used in several domains such as social media analysis, financial analysis, video annotation, surveillance, medical services and traffic prediction. These applications, running on different types of platforms from mobile devices to servers, are characterized by a highly-variable stochastic input data stream, stringent delay constraints and complex task graphs. Several software and hardware optimization techniques have been proposed to maximize the execution quality and the throughput of these applications and to minimize their energy consumption on many-core platforms. By analyzing the existing techniques, one can observe that most solutions classify as a hardware-based task-specific optimization, or as an operating system scheduler optimization, or yet as a load shedding mechanism at the application level. Each of these categories is limited in scope and can be blind to the nature of the program, the data being processed or the characteristics of the hardware. Big-Data streaming applications, due to their wide range of host hardware and content and dynamically-changing input streams, expose the fragmentation of the optimization techniques and create a clear need for a better approach. In this thesis, I propose a suite of energy-efficient hardware-software co-design techniques to bridge the gap between modern Big-Data streaming applications and existing many-core platforms. I choose to model the task graph of the class of applications I consider here by a direct acyclic graph (DAG). First, at the application layer, I propose a unified DAG monitoring solution to process online the general DAG model of the application and provide a set of relevant information that is leveraged at run time by a connected scheduler. At the operating system layer, I propose three different online scheduling solutions for many-core platforms which leverage the feedback from both the application and the hardware layers. The first scheduler addresses the problem of minimizing the energy consumption and the deadlines miss rates of multimedia applications. It takes advantage of the output of the DAG monitoring solution to adapt the mapping of the tasks of multimedia applications to the hardware according to the detected performance and targeted quality of service. The second and third schedulers address the problem of maximizing the quality and throughput and minimizing the energy consumption of Big-Data stream mining applications with single and multiple streams originating from different sources. To cope with the dynamically-changing Big-Data characteristics, the schedulers integrate machine-learning techniques to learn the environment dynamics and the application requirements and adapt the scheduling policy to the desired quality of service. I show that the proposed schedulers are able to scale the execution of data-mining applications to the system capability even in the presence of concept drift. Last, at the hardware layer, to address existing system architectures limitations and to increase even more the throughput, I propose a novel low-power many-core architecture for modern Big-Data stream mining applications that integrates a novel flexible memory hierarchy able to adapt to the dynamic data-driven nature of the input data stream.

A recursive max-linear vector models causal dependence between its components by expressing each node variable as a max-linear function of its parental nodes in a directed acyclic graph and some exogenous innovation. Motivated by extreme value theory, innovations are assumed to have regularly varying distribution tails. We propose a scaling technique in order to determine a causal order of the node variables. All dependence parameters are then estimated from the estimated scalings. Furthermore, we prove asymptotic normality of the estimated scalings and dependence parameters based on asymptotic normality of the empirical spectral measure. Finally, we apply our structure learning and estimation algorithm to financial data and food dietary interview data. (C) 2020 Elsevier Inc. All rights reserved.

Related concepts (44)

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called no

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before