Computing large independent sets in a single round
type: Item
instance of: scholarly article
title: Computing large independent sets in a single round
zbMATH Open document ID: 1423.68340
author: Magnús M. Halldórsson
author: Christian Konrad
published in: Distributed Computing
publication date: 2018-02-23T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 6842773
zbMATH Keywords: maximum independent set
zbMATH Keywords: bounded-independence graphs
zbMATH Keywords: distributed algorithms
zbMATH Keywords: randomized algorithms
MaRDI profile type: Publication
OpenAlex ID: W2599155613
cites work: Beeping a maximal independent set
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: The probabilistic method
cites work: On the Locality of Some NP-Complete Problems
cites work: A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
cites work: Brief Announcement
cites work: Deploying Wireless Networks with Beeps
cites work: Fast Distributed Approximations in Planar Graphs
cites work: An Improved Distributed Algorithm for Maximal Independent Set
cites work: Q3138896
cites work: Streaming algorithms for independent sets in sparse hypergraphs
cites work: Wireless scheduling with power control
cites work: Distributed Algorithms for Coloring Interval Graphs
cites work: Nearly optimal bounds for distributed wireless scheduling in the SINR model
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
cites work: Q4427874
cites work: Reducibility among Combinatorial Problems
cites work: Distributed Contention Resolution in Wireless Networks
cites work: Local Computation
cites work: On the complexity of distributed graph coloring
cites work: Locality in Distributed Graph Algorithms
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: Analysis of fully distributed splitting and naming probabilistic procedures and applications
cites work: Maximal independent sets in radio networks
cites work: What Can be Computed Locally?
cites work: On the Complexity of Distributed Network Decomposition
cites work: An optimal maximal independent set algorithm for bounded-independence graphs
cites work: Survey of local algorithms
cites work: Q3002782
DOI: 10.1007/S00446-017-0298-Y
description: scientific article; zbMATH DE number 6842773