Skip to Main content Skip to Navigation
Journal articles

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

Abstract : We present an algorithm that for 2-colorable 3-uniform hypergraphs, finds a 2-coloring in average running time O (n(5) log(2) n).
Document type :
Journal articles
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990504
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 3:39:42 PM
Last modification on : Monday, December 28, 2020 - 10:22:04 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:12:19 PM

File

1357-6016-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00990504, version 1

Collections

Citation

Yury Person, Mathias Schacht. An expected polynomial time algorithm for coloring 2-colorable 3-graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 2 (2), pp.1--18. ⟨hal-00990504⟩

Share

Metrics

Record views

234

Files downloads

1191