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