Efficient computation of sparse structures

DOI10.1002/RSA.20653MaRDI QIDQ2820273zbMATH OpenOpenAlexFDO

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

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 boundsapproximation algorithmsdistributed algorithmsgraph algorithmsmaximal independent set

Mathematics Subject Classification ID

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

Recommendations

• Efficient computation of balanced structures
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Independent sets in random sparse graphs
• A processor efficient MIS algorithm on random graphs
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

Cites work

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

Cited in

(4)

• Efficient computation of balanced structures
• Efficient data structures for sparse network representation
• Fast multiplication and sparse structures
• Sparse data structure design for wavelet-based methods

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2820273)