Concept

Graphe de Petersen

Publications associées (199)

Edge colorings of graphs without monochromatic stars

In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an ...

ELSEVIER2020

Who Started This Rumor? Quantifying the Natural Differential Privacy of Gossip Protocols

Rachid Guerraoui, Hadrien Hendrikx

Gossip protocols (also called rumor spreading or epidemic protocols) are widely used to disseminate information in massive peer-to-peer networks. These protocols are often claimed to guarantee privacy because of the uncertainty they introduce on the node t ...

Schloss Dagstuhl, Leibniz-Zentrum2020

Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion

Nicolas Aspert, Volodymyr Miz, Benjamin Ricaud

Studying real-world networks such as social networks or web networks is a challenge. These networks often combine a complex, highly connected structure together with a large size. We propose a new approach for large scale networks that is able to automatic ...

2020

Graph Laplacian Mixture Model

Pascal Frossard, Hermina Petric Maretic

Graph learning methods have recently been receiving increasing interest as means to infer structure in datasets. Most of the recent approaches focus on different relationships between a graph and data sample distributions, mostly in settings where all avai ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Materials Cloud, a platform for open computational science

Berend Smit, Nicola Marzari, Giovanni Pizzi, Martin Uhrin, Fernando Gargiulo, Christoph Leopold Talirz, Aliaksandr Yakutovich, Sebastiaan Philippe Huber, Snehal Pramod Kumbhar, Spyros Zoupanos, Elsa Passaro, Daniele Passerone

Materials Cloud is a platform designed to enable open and seamless sharing of resources for computational science, driven by applications in materials modelling. It hosts (1) archival and dissemination services for raw and curated data, together with their ...

2020

Symbolic Algorithms for Token Swapping

Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...

2020

Letter graphs and geometric grid classes of permutations: Characterization and recognition

Dominique de Werra

In this paper, we reveal an intriguing relationship between two seemingly unrelated notions: letter graphs and geometric grid classes of permutations. An important property common for both of them is well-quasi-orderability, implying, in a non-constructive ...

ELSEVIER2020

Improved Ramsey-type results for comparability graphs

Istvan Tomon, Dániel József Korándi

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...

CAMBRIDGE UNIV PRESS2020

Stability results for vertex Turatn problems in Kneser graphs

Abhishek Methuku

The vertex set of the Kneser graph K(n, k) is V = (([n])(k)) and two vertices are adjacent if the corresponding sets are disjoint. For any graph F, the largest size of a vertex set U subset of V such that K(n, k)[U] is F-free, was recently determined by Al ...

ELECTRONIC JOURNAL OF COMBINATORICS2019

Local Approximation of the Maximum Cut in Regular Graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

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