Publication

On the Throughput Improvement due to Limited Complexity Processing at Relay Nodes

Publications associées (93)

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

Sequential metric dimension for random graphs

Patrick Thiran, Gergely Odor

In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...

2021

On the constancy theorem for anisotropic energies through differential inclusions

Riccardo Tione

In this paper we study stationary graphs for functionals of geometric nature defined on currents or varifolds. The point of view we adopt is the one of differential inclusions, introduced in this context in the recent papers (De Lellis et al. in Geometric ...

2021

Adaptive majority problems for restricted query graphs and for weighted sets

Abhishek Methuku, Balázs Keszegh

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

ELSEVIER2021

Edge colorings of graphs without monochromatic stars

Abhishek Methuku

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

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

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

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

Graph Signal Processing: Foundations and Emerging Directions [From the Guest Editors]

Dimitri Nestor Alice Van De Ville, Negar Kiyavash

The articles in this special section focus on graph signal processing. Generically, the networks that sustain our societies can be understood as complex systems formed by multiple nodes, where global network behavior arises from local interactions between ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

Differentially Private Release of Synthetic Graphs

Mikhail Kapralov, Marek Elias

We propose a (epsilon, delta)-differentially private mechanism that, given an input graph G with n vertices and m edges, in polynomial time generates a synthetic graph G' approximating all cuts of the input graph up to an additive error of O (root mn/epsil ...

ASSOC COMPUTING MACHINERY2020