Streaming algorithms for 2-coloring uniform hypergraphs

DOI10.1007/978-3-642-22300-6_57MaRDI QIDQ5199282zbMATH OpenOpenAlexFDO

Authors Saswata Shannigrahi, Jaikumar Radhakrishnan

Publication date 12 August 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22300-6_57

zbMATH Keywords

randomized algorithmstreaming algorithmhypergraph coloringproperty B

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Recommendations

• Improved bounds and algorithms for hypergraph 2-coloring
• Coloring bipartite hypergraphs
• Two‐coloring random hypergraphs
• A note on two-colorability of nonuniform hypergraphs
• On-line algorithms for 2-coloring hypergraphs via chip games

Cited in

(5)

• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• Better streaming algorithms for the maximum coverage problem
• Streaming algorithms for independent sets in sparse hypergraphs
• Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring
• Deterministic graph coloring in the streaming model

This page was built for publication: Streaming algorithms for 2-coloring uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199282)