The price of being near-sighted

DOI10.1145/1109557.1109666zbMath1192.68044OpenAlexW4248332043MaRDI QIDQ3581560

Thomas Moscibroda, Fabian Kuhn, Roger Wattenhofer

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.) (68U35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (49)

Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Can we locally compute sparse connected subgraphs? ⋮ Distributed approximation of capacitated dominating sets ⋮ What can be sampled locally? ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Deterministic local algorithms, unique identifiers, and fractional graph colouring ⋮ Component stability in low-space massively parallel computation ⋮ Graphs with minimum fractional domatic number ⋮ Optimal distributed covering algorithms ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Beeping a maximal independent set ⋮ Almost stable matchings by truncating the Gale-Shapley algorithm ⋮ Simple Neural-Like P Systems for Maximal Independent Set Selection ⋮ Round Compression for Parallel Matching Algorithms ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Leveraging Linial’s Locality Limit ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ Fair Packing and Covering on a Relative Scale ⋮ On the complexity of distributed stable matching with small messages ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ The abstract MAC layer ⋮ Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists ⋮ Constant-time local computation algorithms ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Local approximability of max-min and min-max linear programs ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover ⋮ Sublinear Graph Approximation Algorithms ⋮ A simple local 3-approximation algorithm for vertex cover ⋮ Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs ⋮ Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms ⋮ Leader election in SINR model with arbitrary power control ⋮ Efficient distributed approximation algorithms via probabilistic tree embeddings ⋮ Weak models of distributed computing, with connections to modal logic ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Beep-and-sleep: message and energy efficient set cover ⋮ Beep-and-sleep: message and energy efficient set cover ⋮ A local approximation algorithm for minimum dominating set problem in anonymous planar networks ⋮ Fault-Tolerant Consensus with an Abstract MAC Layer. ⋮ Distributed Approximate Maximum Matching in the CONGEST Model. ⋮ Distributed set cover approximation: Primal-dual with optimal locality ⋮ Set cover problems with small neighborhood covers ⋮ Local planar domination revisited ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming

This page was built for publication: The price of being near-sighted