Simple and local independent set approximation

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

zbMATH Keywords

approximation algorithmindependent setdistributed algorithmTurán bound

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) 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