Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Catégorie

Théorie des graphes

Publications associées (29)

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

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Colin Peter Sandon

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Ieee-Inst Electrical Electronics Engineers Inc2024

Non-planarity of Markoff graphs mod p

Matthew De Courcy-Ireland

We prove the non-planarity of a family of 3-regular graphs constructed from the solutions to the Markoff equation x2 + y2 + z2 = xyz modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these gr ...

European Mathematical Soc-Ems2024

Streaming Algorithms for Connectivity Augmentation

Mikhail Kapralov

We study the k-connectivity augmentation problem (k-CAP) in the single-pass streaming model. Given a (k − 1)-edge connected graph G = (V, E) that is stored in memory, and a stream of weighted edges (also called links) L with weights in {0, 1, . . ., W }, t ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2024

Towards an Understanding of Hydraulic Sensitivity: Graph Theory Contributions to Water Distribution Analysis

Jérôme Chenal

Water distribution systems (WDSs) are complex networks with numerous interconnected junctions and pipes. The robustness and reliability of these systems are critically dependent on their network structure, necessitating detailed analysis for proactive leak ...

MDPI2024

BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

Nicolas Boumal

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

Siam Publications2024

A Note on Lenses in Arrangements of Pairwise Intersecting Circles in the Plane

Rom Pinchasi

Let F be a family of n pairwise intersecting circles in the plane. We show that the number of lenses, that is convex digons, in the arrangement induced by F is at most 2n - 2. This bound is tight. Furthermore, if no two circles in F touch, then the geometr ...

Electronic Journal Of Combinatorics2024

Towards improving full-length ribosome density prediction by bridging sequence and graph-based representations

Mohan Vamsi Nallapareddy, Pierre Vandergheynst, Felix Naef, Cédric Gobet, Francesco Craighero

Translation elongation plays an important role in regulating protein concentrations in the cell, and dysregulation of this process has been linked to several human diseases. In this study, we use data from ribo-seq experiments to model ribosome densities, ...

PMLR2024

Network-based kinetic models: Emergence of a statistical description of the graph topology

Matteo Raviola

In this paper, we propose a novel approach that employs kinetic equations to describe the collective dynamics emerging from graph-mediated pairwise interactions in multi-agent systems. We formally show that for large graphs and specific classes of interact ...

Cambridge Univ Press2024

Molecular hypergraph neural networks

Philippe Schwaller, Junwu Chen

Graph neural networks (GNNs) have demonstrated promising performance across various chemistry-related tasks. However, conventional graphs only model the pairwise connectivity in molecules, failing to adequately represent higher order connections, such as m ...

Aip Publishing2024

Graph generative deep learning models with an application to circuit topologies

Igor Krawczuk

Modern integrated circuits are tiny yet incredibly complex technological artifacts, composed of millions and billions of individual structures working in unison. Managing their complexity and facilitating their design drove part of the co-evolution of mode ...

EPFL2024

Recovering Static and Time-Varying Communities Using Persistent Edges

Maximilien Claude Robert Dreveton

This article focuses on spectral methods for recovering communities in temporal networks. In the case of fixed communities, spectral clustering on the simple time-aggregated graph (i.e., the weighted graph formed by the sum of the interactions over all tem ...

Ieee Computer Soc2024

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

Tony Alan Wood

We develop an algorithm to solve the bottleneck assignment problem (BAP) that is amenable to having computation distributed over a network of agents. This consists of exploring how each component of the algorithm can be distributed, with a focus on one com ...

Ieee-Inst Electrical Electronics Engineers Inc2024

Physics-Enhanced Graph Neural Networks for Soft Sensing in Industrial Internet of Things

Olga Fink, Keivan Faghih Niresi

The Industrial Internet of Things (IIoT) is reshaping manufacturing, industrial processes, and infrastructure management. By fostering new levels of automation, efficiency, and predictive maintenance, IIoT is transforming traditional industries into intell ...

2024

The Strong Integral Input-to-State Stability Property in Dynamical Flow Networks

Nils Gustav Nilsson

Dynamical flow networks serve as macroscopic models for, e.g., transportation networks, queuing networks, and distribution networks. While the flow dynamics in such networks follow the conservation of mass on the links, the outflow from each link is often ...

Ieee-Inst Electrical Electronics Engineers Inc2024

SAT-based Exact Modulo Scheduling Mapping for Resource-Constrained CGRAs

David Atienza Alonso, Giovanni Ansaloni, José Angel Miranda Calero, Benoît Walter Denkinger, Juan Pablo Sapriza Araujo, Ruben Rodriguez, Rubén Rodríguez Álvarez

Coarse-Grain Reconfigurable Arrays (CGRAs) represent emerging low-power architectures designed to accelerate Compute-Intensive Loops (CILs). The effectiveness of CGRAs in providing acceleration relies on the quality of mapping: how efficiently the CIL is c ...

2024

High-Throughput and Flexible Belief Propagation List Decoder for Polar Codes

Andreas Peter Burg, Alexios Konstantinos Balatsoukas Stimming, Yifei Shen, Yuqing Ren, Andreas Toftegaard Kristensen, Leyu Zhang

Due to its high parallelism, belief propagation (BP)decoding is amenable to high-throughput applications and thusrepresents a promising solution for the ultra-high peak datarate required by future communication systems. To bridge theperformance gap compare ...

Ieee-Inst Electrical Electronics Engineers Inc2024

In Medio Stat Virtus: Combining Boolean and Pattern Matching

Giovanni De Micheli, Alessandro Tempia Calvino, Gianluca Radi

Technology mapping transforms a technology-independent representation into a technology-dependent one given a library of cells. This process is performed by means of local replacements that are extracted by matching sections of the subject graph to library ...

IEEE2024

The Privacy Power of Correlated Noise in Decentralized Learning

Rachid Guerraoui, Martin Jaggi, Youssef Allouah, Anastasiia Koloskova

Decentralized learning is appealing as it enables the scalable usage of large amounts of distributed data and resources (without resorting to any central entity), while promoting privacy since every user minimizes the direct exposure of their data. Yet, wi ...

PMLR2024

Graph Exploration for Effective Multiagent Q-Learning

Ali H. Sayed, Ainur Zhaikhan

This article proposes an exploration technique for multiagent reinforcement learning (MARL) with graph-based communication among agents. We assume that the individual rewards received by the agents are independent of the actions by the other agents, while ...

Ieee-Inst Electrical Electronics Engineers Inc2024