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.05024MaRDI 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

hypergraph; randomized algorithm; vertex coloring; Lovász local lemma; expected linear time

Mathematics Subject Classification ID

05C65: Hypergraphs

60C05: Combinatorial probability

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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