The Complexity of Data Aggregation in Directed Networks

DOI10.1007/978-3-642-24100-0_40zbMath1350.68047OpenAlexW191272617MaRDI QIDQ3095346

Fabian Kuhn, Rotem Oshman

Publication date: 28 October 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-24100-0_40

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (12)

Upper and lower bounds for deterministic broadcast in powerline communication networks ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Some lower bounds in dynamic networks with oblivious adversaries ⋮ Distributed Testing of Distance-k Colorings ⋮ Synchronous \(t\)-resilient consensus in arbitrary graphs ⋮ Exploration of dynamic tori by multiple agents ⋮ A topological perspective on distributed network algorithms ⋮ On the treewidth of dynamic graphs ⋮ Bounded-contention coding for the additive network model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• A distributed selection algorithm and its expected communication complexity
• On the distributional complexity of disjointness
• Distributed computation in dynamic networks
• Distributed computation of the mode
• Fast Distributed Algorithms for Computing Separable Functions
• The Probabilistic Communication Complexity of Set Intersection
• Communication Complexity
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• A note on efficient aggregate queries in sensor networks

This page was built for publication: The Complexity of Data Aggregation in Directed Networks