Simple and local independent set approximation
From MaRDI portal
Publication:5919021
DOI10.1016/j.tcs.2020.09.018zbMath1464.68275arXiv1803.00786OpenAlexW4205557525MaRDI QIDQ5919021
Magnús M. Halldórsson, Dror Rawitz, Ravi B. Boppana
Publication date: 6 November 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1803.00786
Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Streaming algorithms for independent sets in sparse hypergraphs
- An optimal bit complexity randomized distributed MIS algorithm
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Small transversals in hypergraphs
- On approximation properties of the independent set problem for low degree graphs
- A probabilistic lower bound on the independence number of graphs
- Computing large independent sets in a single round
- Lower bounds on the independence number in terms of the degrees
- A note on greedy algorithms for the maximum weighted independent set problem
- On the Lovász Theta function for Independent Sets in Sparse Graphs
- Online Set Packing
- Local Computation
- Approximation Resistance from Pairwise-Independent Subgroups
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Distributed Computing: A Locality-Sensitive Approach
- On Constant Time Approximation of Parameters of Bounded Degree Graphs
- On the complexity of local distributed graph problems
- Hardness of Distributed Optimization
- Brief Announcement
- Distributed Approximation of Maximum Independent Set and Maximum Matching
This page was built for publication: Simple and local independent set approximation
