Concept

Mineur (théorie des graphes)

Publications associées (143)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Distributed Inference over Multitask Graphs under Smoothness

Ali H. Sayed, Stefan Vlaski, Roula Nassif

This paper formulates a multitask optimization problem where agents in the network have individual objectives to meet, or individual parameter vectors to estimate, subject to a smoothness condition over the graph. The smoothness requirement softens the tra ...

IEEE2018

The Sketching Complexity of Graph and Hypergraph Counting

Mikhail Kapralov, John Michael Goddard Kallaugher

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been ...

IEEE COMPUTER SOC2018

Random sampling of bandlimited signals on graphs

Pierre Vandergheynst, Rémi Gribonval, Gilles Puy, Nicolas Tremblay

We study the problem of sampling k-bandlimited signals on graphs. We propose two sampling strategies that consist in selecting a small subset of nodes at random. The first strategy is non-adaptive, i.e., independent of the graph structure, and its performa ...

Elsevier2018

Monochromatic cycle covers in random graphs

Dániel József Korándi

A classic result of Erdos, Gyarfas and Pyber states that for every coloring of the edges of K-n with r colors, there is a cover of its vertex set by at most f(r)=O(r2logr) vertex-disjoint monochromatic cycles. In particular, the minimum number of such cove ...

WILEY2018

Many disjoint edges in topological graphs

Andres Jacinto Ruiz Vargas

A monotone cylindrical graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called simple if any pair of its edges have at most one ...

Elsevier Science Bv2017

Method and System for Fault Detection and Faulted Line Identification in Power Systems using Synchrophasors-Based Real-Time State Estimation

Mario Paolone, Paolo Romano, Marco Pignati, Lorenzo Zanni

A method for a faulted line identification in a power network, including, at a generic time-instant, solving a plurality of parallel phasor measurement units based real-time state estimators, the state estimators having among each other different and augme ...

2017

Linker call graph with full Dotty support

Nicolas Alexander Stucki

This project consisted in bringing the linker call graph up to date with dotty/master, restructure the code, make it support the full Scala language and make it support calls to Java code. Also implemented dead code elimination of unreachable methods based ...

2017

Graph-based structures in data science

Nathanaël Perraudin

State-of-the-art data analysis tools have to deal with high-dimensional data. Fortunately, the inherent dimensionality of data is often much smaller, as it has an internal structure limiting its degrees of freedom. In most cases, this structure can be appr ...

EPFL2017

The weighted stable matching problem

Linda Farczadi

We study the stable matching problem in non-bipartite graphs with incomplete but strict preference lists, where the edges have weights and the goal is to compute a stable matching of minimum or maximum weight. This problem is known to be NP-hard in general ...

2017

Simple topological graphs

Andres Jacinto Ruiz Vargas

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any t ...

EPFL2016