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 Verlag2015Linear Function Computation in Networks: Duality and Constant Gap Results
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 Engineers2013Optimizing 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 -relay diamond networks. Focusing on vector Gaussian quantization at the relays, our goal is to understand how close to the cutset up ...
2012Optimizing 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 ...
Ieee2012Maintaining minimum spanning forests in dynamic graphs
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. ...
2001Randomized fully dynamic graph algorithms with polylogarithmic time per operation
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 ...
1999Average-case analysis of dynamic graph algorithms
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