Streaming algorithms for 2-coloring uniform hypergraphs

DOI10.1007/978-3-642-22300-6_57zbMATH Open1342.05186OpenAlexW49889426MaRDI QIDQ5199282FDOQ5199282

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

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

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)

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)