Distributed Computing

DOI10.1007/11561927zbMath1171.68861MaRDI QIDQ5395154

Roger Wattenhofer, Thomas Moscibroda, Fabian Kuhn, Tim Nieberg

Publication date: 1 November 2006

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

Full work available at URL: https://doi.org/10.1007/11561927

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W15: Distributed algorithms

Related Items

Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds, Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings, Shifting strategy for geometric graphs without geometry, Distributed approximation of capacitated dominating sets, An optimal bit complexity randomized distributed MIS algorithm, The abstract MAC layer, Fast deterministic distributed algorithms for sparse spanners, An optimal maximal independent set algorithm for bounded-independence graphs, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition, Empire of colonies: Self-stabilizing and self-organizing distributed algorithm, The coverage-control optimization in sensor network subject to sensing area, A weakly robust PTAS for minimum clique partition in unit disk graphs, Beeping a maximal independent set, On the computation of fixed points in Boolean networks, An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract), Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs, Fast Distributed Approximations in Planar Graphs