Discrete Mathematics & Theoretical Computer Science, Vol 13, No 2 (2011)

Font Size:  Small  Medium  Large

An expected polynomial time algorithm for coloring 2-colorable 3-graphs

Yury Aleksandrovic Person, Mathias Schacht

Abstract


We present an algorithm that for 2-colorable 3-uniform hypergraphs, finds a 2-coloring in average running time O(n5log2 n).

Full Text: PDF PostScript