Efficient computation of sparse structures

DOI10.1002/rsa.20653zbMath1346.05215OpenAlexW2337885251MaRDI QIDQ2820273

Peter Robinson, Ehab Morsy, David G. Harris, Aravind Srinivasan, Gopal Pandurangan

Publication date: 15 September 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20653

zbMATH Keywords

randomizationlower boundsgraph algorithmsapproximation algorithmsdistributed algorithmsmaximal independent set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Towards optimal lower bounds for clique and chromatic number.
• Turan's theorem for \(k\)-graphs
• Survey of local algorithms
• 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 parallel algorithm for the maximal independent set problem
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Distributed Computing: A Locality-Sensitive Approach

This page was built for publication: Efficient computation of sparse structures