Concept
Cycle (théorie des graphes)
Publications associées (91)
The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.
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 ...
Elsevier2024Better Trees for Santa Claus
Etienne Michel François Bamas, Lars Rohwedder
We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...
New York2023Expanding computational biochemistry towards complex and non-natural compounds
In the beginning was the metabolism. The biochemical processes that make life possible transformed the soup of chemicals into the life on Earth we know today. Since then, living organisms have evolved, and life on Earth has become more complex. Living orga ...
EPFL2023Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles
Paolo Ienne, Kubilay Atasu, Jovan Blanusa
Finding cycles in directed graphs enables important applications in various domains such as finance, biology, chemistry, and network science. However, as the size of graph datasets continues to grow, it becomes increasingly difficult to discover cycles wit ...
arXiv2023Toward 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 INC2022Propagation on Multi-relational Graphs for Node Regression
Recent years have witnessed a rise in real-world data captured with rich structural information that can be conveniently depicted by multi-relational graphs. While inference of continuous node features across a simple graph is rather under-studied by the c ...
2021Estimating an extreme Bayesian network via scalings
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 INC2021On Representation Learning for Scientific News Articles Using Heterogeneous Knowledge Graphs
Karl Aberer, Angeliki Romanou, Panagiotis Smeros
In the era of misinformation and information inflation, the credibility assessment of the produced news is of the essence. However, fact-checking can be challenging considering the limited references presented in the news. This challenge can be transcended ...
ASSOC COMPUTING MACHINERY2021Representation Learning for Multi-relational Data
Recent years have witnessed a rise in real-world data captured with rich structural information that can be better depicted by multi-relational or heterogeneous graphs.However, research on relational representation learning has so far mostly focused on the ...
EPFL2021Large-Scale Graph Processing on FPGAs with Caches for Thousands of Simultaneous Misses
Efficient large-scale graph processing is crucial to many disciplines. Yet, while graph algorithms naturally expose massive parallelism opportunities, their performance is limited by the memory system because of irregular memory accesses. State-of-the-art ...
IEEE COMPUTER SOC2021