On the locality of bounded growth

DOI10.1145/1073814.1073826zbMath1314.68160OpenAlexW2114986147MaRDI QIDQ5177224

Roger Wattenhofer, Fabian Kuhn, Thomas Moscibroda

Publication date: 10 March 2015

Published in: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1073814.1073826

zbMATH Keywords

coveringpackinglocalitydistributed algorithmsdoubling dimensionmaximal independent setdominating setsnetwork decompositionbounded growthunit disk graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Related Items (18)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Distributed construction of low-interference spanners ⋮ Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Coloring unstructured radio networks ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Distributed approximation of capacitated dominating sets ⋮ Distributed strong diameter network decomposition ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Shifting strategy for geometric graphs without geometry ⋮ Using the doubling dimension to analyze the generalization of learning algorithms ⋮ Leveraging Linial’s Locality Limit ⋮ Low-congestion shortcut and graph parameters ⋮ 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 ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Unnamed Item

This page was built for publication: On the locality of bounded growth