An algorithmic approach to the Lovász local lemma. I
From MaRDI portal
Publication:3986105
DOI10.1002/rsa.3240020402zbMath0756.05080OpenAlexW2022392080WikidataQ56565511 ScholiaQ56565511MaRDI QIDQ3986105
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.3240020402
Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (49)
An \(O(n\log n)\) algorithm for finding dissimilar strings ⋮ Covering with Latin transversals ⋮ Weighted fractional and integral \(k\)-matching in hypergraphs ⋮ Coloring and the Lovász local lemma ⋮ Colouring Non-sparse Random Intersection Graphs ⋮ Hypergraph colouring and the Lovász local lemma ⋮ Rainbow Hamilton cycles and lopsidependency ⋮ Independent transversals in \(r\)-partite graphs ⋮ Efficient delay routing ⋮ Bandwidth and low dimensional embedding ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Unnamed Item ⋮ Acyclic vertex coloring of graphs of maximum degree 5 ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Unnamed Item ⋮ Arithmetic Progressions and Tic-Tac-Toe Games ⋮ Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory ⋮ Randomly colouring graphs (a combinatorial view) ⋮ Colouring graphs when the number of colours is almost the maximum degree ⋮ Reroute sequence planning in telecommunication networks and compact vector summation. ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming ⋮ Coloring bipartite hypergraphs ⋮ Acyclic edge colorings of graphs ⋮ On existence theorems ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ A Kolmogorov complexity proof of the Lovász local lemma for satisfiability ⋮ Asymptotically optimal frugal colouring ⋮ The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma ⋮ The role assignment model nearly fits most social networks ⋮ Testing hypergraph colorability ⋮ On the benefit of supporting virtual channels in wormhole routers ⋮ Entropy compression versus Lovász local lemma ⋮ The acyclic edge chromatic number of a random d‐regular graph is d + 1 ⋮ 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] ⋮ Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas ⋮ Local embeddings of metric spaces ⋮ Ergodic theorems for the shift action and pointwise versions of the Abért-Weiss theorem ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Bandwidth and Low Dimensional Embedding ⋮ The Lovász Local Lemma and Satisfiability ⋮ Colouring a graph frugally ⋮ Finding independent transversals efficiently ⋮ Choosability in random hypergraphs ⋮ Unnamed Item ⋮ Distributed coloring algorithms for triangle-free graphs ⋮ Probabilistic methods in coloring and decomposition problems
Cites Work
This page was built for publication: An algorithmic approach to the Lovász local lemma. I
