Publication

Fully dynamic cycle-equivalence in graphs

Related publications (137)

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.

Vector-Based 3D Graphic Statics: a framework for the design of spatial structures based on the relation between form and forces

Corentin Jean Dominique Fivet, Pierluigi D'Acunto

This article develops a vector-based 3D graphic statics framework that uses synthetic and intuitive graphical means for the analysis and design of spatial structures such as networks of bar elements in static equilibrium. It is intended to support the coll ...

2019

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approxi ...

2019

Distributed Diffusion Adaptation Over Graph Signals

Ali H. Sayed, Jie Chen, Roula Nassif

Most works on graph signal processing assume static graph signals, which is a limitation even in comparison to traditional DSP techniques where signals are modeled as sequences that evolve over time. For broader applicability, it is necessary to develop te ...

IEEE2018

Spectrally approximating large graphs with smaller graphs

Pierre Vandergheynst, Andreas Loukas

How does coarsening affect the spectrum of a general graph? We provide conditions such that the principal eigenvalues and eigenspaces of a coarsened and original graph Laplacian matrices are close. The achieved approximation is shown to depend on standard ...

2018

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

Graph Heat Mixture Model Learning

Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic

Graph inference methods have recently attracted a great interest from the scientific community, due to the large value they bring in data interpretation and analysis. However, most of the available state-of-the-art methods focus on scenarios where all avai ...

IEEE2018

Note on k-planar crossing numbers

János Pach

The crossing number CR(G) of a graph G = (V, E) is the smallest number of edge crossings over all drawings of G in the plane. For any k >= 1, the k-planar crossing number of G, CRk(G), is defined as the minimum of CR(G(0)) + CR(G(1)) + ... + CR(G(k-i)) ove ...

Elsevier Science Bv2018

Learning time varying graphs

Pascal Frossard, Andreas Loukas, Vasilis Kalofolias

We consider the problem of inferring the hidden structure of high-dimensional dynamic systems from the perspective of graph learning. In particular, we aim at capturing the dynamic relationships between nodes by a sequence of graphs. Our approach is motiva ...

Ieee2017

Belief control strategies for interactions over weak graphs

Ali H. Sayed

In diffusion social learning over weakly-connected graphs, it has been shown that influential agents end up shaping the beliefs of non-influential agents. In this paper, we analyse this control mechanism more closely and reveal some critical properties. In ...

IEEE2017

Social Learning Over Weakly Connected Graphs

Ali H. Sayed, Bicheng Ying

In this paper, we study diffusion social learning over weakly connected graphs. We show that the asymmetric flow of information hinders the learning abilities of certain agents regardless of their local observations. Under some circumstances that we clarif ...

2017