Computing large independent sets in a single round

DOI10.1007/s00446-017-0298-yzbMath1423.68340OpenAlexW2599155613MaRDI QIDQ1699422

Christian Konrad, Magnús M. Halldórsson

Publication date: 23 February 2018

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

Full work available at URL: https://research-information.bris.ac.uk/en/publications/de4d7937-6500-4f75-88ca-fddd326b61f7

zbMATH Keywords

randomized algorithmsdistributed algorithmsmaximum independent setbounded-independence graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Unnamed Item, Simple and local independent set approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nearly optimal bounds for distributed wireless scheduling in the SINR model
• Streaming algorithms for independent sets in sparse hypergraphs
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• An optimal maximal independent set algorithm for bounded-independence graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Analysis of fully distributed splitting and naming probabilistic procedures and applications
• Beeping a maximal independent set
• Survey of local algorithms
• Wireless scheduling with power control
• On the Locality of Some NP-Complete Problems
• Local Computation
• A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
• Fast Distributed Approximations in Planar Graphs
• Deploying Wireless Networks with Beeps
• Distributed Contention Resolution in Wireless Networks
• 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
• An Improved Distributed Algorithm for Maximal Independent Set
• What Can be Computed Locally?
• On the Complexity of Distributed Network Decomposition
• Reducibility among Combinatorial Problems
• Maximal independent sets in radio networks
• On the complexity of distributed graph coloring
• Brief Announcement
• Brief Announcement
• Distributed Algorithms for Coloring Interval Graphs