Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma

DOI<213::AID-RSA3>3.0.CO;2-Y 10.1002/1098-2418(200010/12)17:3/4<213::AID-RSA3>3.0.CO;2-YzbMath0964.05024OpenAlexW2000992447MaRDI QIDQ4521547

Artur Czumaj, Christian Scheideler

Publication date: 8 July 2001

Full work available at URL: https://doi.org/10.1002/1098-2418(200010/12)17:3/4<213::aid-rsa3>3.0.co;2-y

zbMATH Keywords

hypergraphrandomized algorithmvertex coloringLovász local lemmaexpected linear time

Mathematics Subject Classification ID

Hypergraphs (05C65) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

An estimate for the probability of dependent events ⋮ Testing hypergraph colorability

Cites Work

• Lopsided Lovász Local lemma and Latin transversals
• Colouring a graph frugally
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Acyclic coloring of graphs
• An algorithmic approach to the Lovász local lemma. I
• A parallel algorithmic version of the local lemma
• Simple Constructions of Almost k-wise Independent Random Variables
• Efficient approximation of product distributions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma