Computing large independent sets in a single round

DOI10.1007/S00446-017-0298-YMaRDI QIDQ1699422zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Christian Konrad

Publication date 23 February 2018

Published in Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

bounded-independence graphsdistributed algorithmsmaximum independent setrandomized algorithms

Mathematics Subject Classification ID

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

Recommendations

• Distributed large independent sets in one round on bounded-independence graphs
• Brief Announcement
• Brief announcement: Simple and local independent set approximation
• Simple and local independent set approximation
• An optimal maximal independent set algorithm for bounded-independence graphs

Cites work

• \textsc{Maximal Independent Sets} in radio networks
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• An Improved Distributed Algorithm for Maximal Independent Set
• An optimal maximal independent set algorithm for bounded-independence graphs
• Analysis of fully distributed splitting and naming probabilistic procedures and applications
• Brief Announcement
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Deploying wireless networks with beeps
• Distributed algorithms for coloring interval graphs
• Distributed contention resolution in wireless networks
• Fast Distributed Approximations in Planar Graphs
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• scientific article; zbMATH DE number 432768 (Why is no real title available?)
• scientific article; zbMATH DE number 1979528 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Local computation: lower and upper bounds
• Locality in Distributed Graph Algorithms
• On the complexity of distributed graph coloring
• On the Complexity of Distributed Network Decomposition
• On the locality of some NP-complete problems
• Reducibility among combinatorial problems
• Streaming algorithms for independent sets in sparse hypergraphs
• Survey of local algorithms
• The probabilistic method
• What Can be Computed Locally?
• Wireless scheduling with power control

Cited in

(4)

• Distributed large independent sets in one round on bounded-independence graphs
• Independent sets in vertex-arrival streams
• Simple and local independent set approximation
• Improved distributed approximations for maximum independent set

This page was built for publication: Computing large independent sets in a single round

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699422)