Concept

Dynamic connectivity

Publications associées (7)

Enforcing Efficient Equilibria in Network Design Games via Subsidies

The efficient design of networks has been an important engineering task that involves challenging combinatorial optimization problems. Typically, a network designer has to select among several alternatives which links to establish so that the resulting net ...

Springer Verlag2015

Linear Function Computation in Networks: Duality and Constant Gap Results

Michael Christoph Gastpar

In linear function computation, multiple source nodes communicate across a relay network to a single destination whose goal is to recover linear functions of the original source data. When the relay network is a linear deterministic network, a duality rela ...

Institute of Electrical and Electronics Engineers2013

Optimizing Quantize-Map-and-Forward Relaying for Gaussian Diamond Networks

Christina Fragouli, Ayan Sengupta, I-Hsiang Wang

We evaluate the information-theoretic achievable rates of Quantize-Map-and-Forward (QMF) relaying schemes over Gaussian

N

-relay diamond networks. Focusing on vector Gaussian quantization at the relays, our goal is to understand how close to the cutset up ...

2012

Optimizing Quantize-Map-and-Forward Relaying for Gaussian Diamond Networks

Christina Fragouli, Ayan Sengupta, I-Hsiang Wang

We evaluate the information-theoretic achievable rates of Quantize-Map-and-Forward (QMF) relaying schemes over Gaussian N-relay diamond networks. Focusing on vector Gaussian quantization at the relays, our goal is to understand how close to the cutset uppe ...

Ieee2012

Maintaining minimum spanning forests in dynamic graphs

Monika Henzinger

We present the first fully dynamic algorithm for maintaining a minimum spanning forest in time o(sqrt(n)) per operation. To be precise, the algorithm uses O(n1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. ...

2001

Randomized fully dynamic graph algorithms with polylogarithmic time per operation

Monika Henzinger

This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletio ...

1999

Average-case analysis of dynamic graph algorithms

Monika Henzinger

We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1 ...

1998

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

Optimizing Quantize-Map-and-Forward Relaying for Gaussian Diamond Networks

Christina Fragouli, Ayan Sengupta, I-Hsiang Wang

We evaluate the information-theoretic achievable rates of Quantize-Map-and-Forward (QMF) relaying schemes over Gaussian

N

-relay diamond networks. Focusing on vector Gaussian quantization at the relays, our goal is to understand how close to the cutset up ...

2012