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

randomized algorithmsdistributed algorithmsmaximum independent setbounded-independence graphs

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 432768 (Why is no real title available?)
• scientific article; zbMATH DE number 1979528 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• 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)
• 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
• 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 Network Decomposition
• On the complexity of distributed graph coloring
• 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
• \textsc{Maximal Independent Sets} in radio networks

Cited in

(4)

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

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)