A parallel algorithmic version of the local lemma

DOI10.1002/RSA.3240020403MaRDI QIDQ3986106zbMATH OpenOpenAlexWikidataFDO

Authors Noga Alon

Publication date 27 June 1992

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

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

zbMATH Keywords

parallel algorithmhypergraphscoloringlocal lemmastar arboricity

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Hypergraphs (05C65) Distributed algorithms (68W15) Applications of graph theory to circuits and networks (94C15)

Recommendations

• An algorithmic approach to the Lovász local lemma. I
• scientific article; zbMATH DE number 1445282
• scientific article; zbMATH DE number 1775440

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Cycles of length 0 modulo k in directed graphs
• Every 7-regular digraph contains an even cycle
• Sign-nonsingular matrices and even cycles in directed graphs
• Single round simulation on radio networks
• The linear arboricity of graphs
• The star arboricity of graphs
• The strong chromatic number of a graph

Cited in

(40)

• Counting hypergraph colorings in the local lemma regime
• An algorithmic approach to the Lovász local lemma. I
• The Lovász-Local-Lemma and Scheduling
• Coloring and the Lovász local lemma
• The strong chromatic number of a graph
• scientific article; zbMATH DE number 1775440 (Why is no real title available?)
• Acyclic edge coloring of graphs with large girths
• A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
• Entropy compression versus Lovász local lemma
• Local conditions for planar graphs of acyclic edge coloring
• Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma
• Near-optimal list colorings
• Space-efficient local computation algorithms
• Distributed algorithms for the Lovász local lemma and graph coloring
• Percolation on finite graphs and isoperimetric inequalities.
• An improved bound on acyclic chromatic index of planar graphs
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• A (1 + ?)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lov�sz Local Lemma
• Hypergraph colouring and the Lovász local lemma
• Random subshifts of finite type
• Acyclic edge coloring of planar graphs with girth at least 5
• Sign rank versus Vapnik-Chervonenkis dimension
• Connectivity graph-codes
• Acyclic edge coloring of planar graphs without small cycles
• Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
• A constructive proof of the general Lovász local lemma
• A local lemma for focused stochastic algorithms
• Weighted fractional and integral k-matching in hypergraphs
• The Lovász Local Lemma and Satisfiability
• Acyclic edge colorings of graphs
• Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
• The number of disk graphs
• Acyclic chromatic index of planar graphs with triangles
• On the benefit of supporting virtual channels in wormhole routers
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• Commutative algorithms approximate the LLL-distribution
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Colouring a graph frugally
• Counting solutions to random CNF formulas
• Local computation algorithms for graphs of non-constant degrees

This page was built for publication: A parallel algorithmic version of the local lemma

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