Leveraging Linial’s Locality Limit

DOI10.1007/978-3-540-87779-0_27zbMath1161.68344OpenAlexW1502920553MaRDI QIDQ3540245

Christoph Lenzen, Roger Wattenhofer

Publication date: 20 November 2008

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

Full work available at URL: https://doi.org/10.1007/978-3-540-87779-0_27

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14)

Related Items (25)

Node labels in local decision ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ What can be verified locally? ⋮ Distributed approximation of capacitated dominating sets ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Deterministic Massively Parallel Connectivity ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs ⋮ A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs ⋮ A hierarchy of local decision ⋮ Local approximability of max-min and min-max linear programs ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover ⋮ A simple local 3-approximation algorithm for vertex cover ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ An optimal maximal independent set algorithm for bounded-independence graphs ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ Improved distributed approximations for maximum independent set ⋮ Distributed domination on sparse graph classes ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks ⋮ Fast Distributed Approximations in Planar Graphs ⋮ Constant round distributed domination on graph classes with bounded expansion

Cites Work

• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Fast Distributed Approximations in Planar Graphs
• The price of being near-sighted
• Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• What Can be Computed Locally?
• An efficient distributed algorithm for constructing small dominating sets
• On the locality of bounded growth
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• What cannot be computed locally!
• Constant-time distributed dominating set approximation

This page was built for publication: Leveraging Linial’s Locality Limit