Linear-in-\(\varDelta \) lower bounds in the LOCAL model

DOI10.1007/s00446-015-0245-8zbMath1423.68192OpenAlexW3122785907MaRDI QIDQ1689747

Juho Hirvonen, Mika Göös, Jukka Suomela

Publication date: 17 January 2018

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-015-0245-8

zbMATH Keywords

lower boundslocal distributed algorithmsmaximal edge packingmaximal fractional matching

Mathematics Subject Classification ID

Related Items (4)

Distributed half-integral matching and beyond ⋮ Distributed half-integral matching and beyond ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ A topological perspective on distributed network algorithms

Cites Work

• Unnamed Item
• Local approximability of max-min and min-max linear programs
• A fast and simple randomized parallel algorithm for maximal matching
• On the Distributed Complexity of Computing Maximal Matchings
• Deterministic Local Algorithms, Unique Identifiers, and Fractional Graph Colouring
• Distributed maximal matching
• Lower bounds for local approximation
• Linear-in-delta lower bounds in the LOCAL model
• Local Computation
• The Locality of Distributed Symmetry Breaking
• Fast Distributed Approximations in Planar Graphs
• Leveraging Linial’s Locality Limit
• The price of being near-sighted
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• What Can be Computed Locally?
• No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Some simple distributed algorithms for sparse networks
• On the complexity of distributed graph coloring
• What cannot be computed locally!
• On Ordered Groups

This page was built for publication: Linear-in-\(\varDelta \) lower bounds in the LOCAL model