A parallel algorithmic version of the local lemma
From MaRDI portal
Publication:3986106
DOI10.1002/rsa.3240020403zbMath0768.05086OpenAlexW2128452148WikidataQ124968806 ScholiaQ124968806MaRDI QIDQ3986106
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
Hypergraphs (05C65) Paths and cycles (05C38) Parallel numerical computation (65Y05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Directed graphs (digraphs), tournaments (05C20) Distributed algorithms (68W15)
Related Items (34)
Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps ⋮ Percolation on finite graphs and isoperimetric inequalities. ⋮ Weighted fractional and integral \(k\)-matching in hypergraphs ⋮ Local conditions for planar graphs of acyclic edge coloring ⋮ Coloring and the Lovász local lemma ⋮ An algorithmic approach to the Lovász local lemma. I ⋮ Hypergraph colouring and the Lovász local lemma ⋮ The strong chromatic number of a graph ⋮ Acyclic edge coloring of planar graphs without small cycles ⋮ Counting Solutions to Random CNF Formulas ⋮ Acyclic edge coloring of graphs with large girths ⋮ Random subshifts of finite type ⋮ Acyclic chromatic index of planar graphs with triangles ⋮ An improved bound on acyclic chromatic index of planar graphs ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Unnamed Item ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ Acyclic edge coloring of planar graphs with girth at least 5 ⋮ Acyclic edge colorings of graphs ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ A Kolmogorov complexity proof of the Lovász local lemma for satisfiability ⋮ The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma ⋮ On the benefit of supporting virtual channels in wormhole routers ⋮ Entropy compression versus Lovász local lemma ⋮ Near-optimal list colorings ⋮ [https://portal.mardi4nfdi.de/wiki/Publication:4521547 Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma] ⋮ The number of disk graphs ⋮ Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ The Lovász Local Lemma and Satisfiability ⋮ Counting Hypergraph Colorings in the Local Lemma Regime ⋮ Colouring a graph frugally ⋮ A Local Lemma for Focused Stochastic Algorithms ⋮ Unnamed Item
Cites Work
- Sign-nonsingular matrices and even cycles in directed graphs
- Cycles of length 0 modulo k in directed graphs
- The linear arboricity of graphs
- Every 7-regular digraph contains an even cycle
- The star arboricity of graphs
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- The strong chromatic number of a graph
- Single round simulation on radio networks
This page was built for publication: A parallel algorithmic version of the local lemma
