Distributed Computing

DOI10.1007/11561927zbMath1171.68861OpenAlexW4245215744MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Related Items (26)

Distributed independent sets in interval and segment intersection graphs ⋮ Design patterns in beeping algorithms: examples, emulation, and analysis ⋮ Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds ⋮ Can we locally compute sparse connected subgraphs? ⋮ Distributed approximation of capacitated dominating sets ⋮ Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings ⋮ A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Beeping a maximal independent set ⋮ Shifting strategy for geometric graphs without geometry ⋮ Simple Neural-Like P Systems for Maximal Independent Set Selection ⋮ An optimal bit complexity randomized distributed MIS algorithm ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ The abstract MAC layer ⋮ Sublinear search spaces for shortest path planning in grid and road networks ⋮ Low-congestion shortcut and graph parameters ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs ⋮ An optimal maximal independent set algorithm for bounded-independence graphs ⋮ Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ On the computation of fixed points in Boolean networks ⋮ Empire of colonies: Self-stabilizing and self-organizing distributed algorithm ⋮ The coverage-control optimization in sensor network subject to sensing area ⋮ An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract) ⋮ Fast Distributed Approximations in Planar Graphs ⋮ Unnamed Item

This page was built for publication: Distributed Computing