Concept

Acyclic orientation

Related publications (32)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

Lukas Fritz Felix Vogl

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Negar Kiyavash, Ehsan Mokhtarian, Saber Salehkaleybar

We study experiment design for unique identification of the causal graph of a system where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skele ...

2022

Toward Mobile Distributed Ledgers

Boi Faltings, Sujit Prakash Gujar, Dimitrios Chatzopoulos, Anurag Jain

Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on Device-to-Device (D2D) ecosystems (e.g., crowdsensing). Sophisticated applications, like cryptocurrencies, need distr ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Lamplighters and the bounded cohomology of Thompson's group

Nicolas Monod

We prove the vanishing of the bounded cohomology of lamplighter groups for a wide range of coefficients. This implies the same vanishing for a number of groups with self-similarity properties, such as Thompson's group F. In particular, these groups are bou ...

SPRINGER BASEL AG2022

Estimating an extreme Bayesian network via scalings

Mario Krali

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

ELSEVIER INC2021

Mneme: A Mobile Distributed Ledger

Boi Faltings, Sujit Prakash Gujar, Dimitrios Chatzopoulos

Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). More sophisticated applications, like cryptocurrencies, need ...

IEEE2020

Counting and Sampling from Markov Equivalent DAGs Using Clique Trees

Negar Kiyavash, Saber Salehkaleybar, Kun Zhang

A directed acyclic graph (DAG) is the most common graphical model for representing causal relationships among a set of variables. When restricted to using only observational data, the structure of the ground truth DAG is identifiable only up to Markov equi ...

AAAI Press2019

Exact Synthesis of LTL Properties from Traces

Heinz Riener

We present an exact approach to synthesize temporal-logic formulas in linear temporal logic (LTL) from a set of given positive and negative example traces. Our approach uses topology structures, in particular partial DAGs, to partition the search space int ...

IEEE2019

Injective And Projective Model Structures On Enriched Diagram Categories

Lyne Moser

In the enriched setting, the notions of injective and projective model structures on a category of enriched diagrams also make sense. In this paper, we prove the existence of these model structures on enriched diagram categories under local presentability, ...

2019

Execution Trace Graph of Dataflow Process Networks

Marco Mattavelli, Simone Casale Brunet

The paper introduces and specifies a formalism that provides complete representations of dataflow process network (DPN) program executions, by means of directed acyclic graphs. Such graphs, also known as execution trace graphs (ETG), are composed of nodes ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2018