Distributed Computing

DOI10.1007/11561927zbMath1171.68861MaRDI QIDQ5395154

Tim Nieberg, Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer

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

Simple Neural-Like P Systems for Maximal Independent Set Selection, Unnamed Item, 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, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, Distributed approximation of capacitated dominating sets, An optimal bit complexity randomized distributed MIS algorithm, The abstract MAC layer, Distributed independent sets in interval and segment intersection graphs, 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, Design patterns in beeping algorithms: examples, emulation, and analysis, Deterministic distributed construction of \(T\)-dominating sets in time \(T\), Sublinear search spaces for shortest path planning in grid and road networks, Low-congestion shortcut and graph parameters, Can we locally compute sparse connected subgraphs?, 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