A parallel algorithmic version of the local lemma
From MaRDI portal
Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Parallel numerical computation (65Y05) Distributed algorithms (68W15) Applications of graph theory to circuits and networks (94C15)
Recommendations
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
(46)- Colouring a graph frugally
- Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
- Weighted fractional and integral k-matching in hypergraphs
- Hypergraph colouring and the Lovász local lemma
- Percolation on finite graphs and isoperimetric inequalities.
- Acyclic edge coloring of planar graphs without small cycles
- Acyclic edge coloring of graphs with large girths
- Acyclic chromatic index of planar graphs with triangles
- An improved bound on acyclic chromatic index of planar graphs
- Entropy compression versus Lovász local lemma
- Local conditions for planar graphs of acyclic edge coloring
- Acyclic edge coloring of planar graphs with girth at least 5
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- The number of disk graphs
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- Acyclic edge colorings of graphs
- A constructive proof of the general Lovász local lemma
- The Lovász Local Lemma and Satisfiability
- An algorithmic approach to the Lovász local lemma. I
- The strong chromatic number of a graph
- Random subshifts of finite type
- Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
- Near-optimal list colorings
- scientific article; zbMATH DE number 1775440 (Why is no real title available?)
- Sign rank versus Vapnik-Chervonenkis dimension
- A (1 + ?)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lov�sz Local Lemma
- Commutative algorithms approximate the LLL-distribution
- Counting solutions to random CNF formulas
- Counting hypergraph colorings in the local lemma regime
- Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma
- A local lemma for focused stochastic algorithms
- Local computation algorithms for graphs of non-constant degrees
- The Lovász-Local-Lemma and Scheduling
- Space-efficient local computation algorithms
- Distributed algorithms for the Lovász local lemma and graph coloring
- On the benefit of supporting virtual channels in wormhole routers
- Connectivity graph-codes
- Counting solutions to random CNF formulas
- Variable version Lovász local lemma: a tale of two boundaries
- A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
- Toward derandomizing Markov chain Monte Carlo
- Inapproximability of counting hypergraph colourings
- Coloring graphs from random lists
- Locally computing edge orientations
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
- Coloring and the Lovász local lemma
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)
