Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. An expected polynomi ...
Article

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

Yury Person ORCID (1), Mathias Schacht ORCID (2) (3)
(1) Institut für Mathematik [Berlin]
(2) Fachbereich Mathematik [Hamburg]
(3) Fachbereich Mathematik = Department of Mathematics [Hamburg]
Download article
Open on HAL
Imported on
September 3, 2009
Published on
May 4, 2011
Last modified on
March 31, 2025
Volume 13
vol. 13:2
Graph and Algorithms
DOI
10.46298/dmtcs.558
License
https://about.hal.science/hal-authorisation-v1
Indicators
1029
Views
1128
Downloads

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

Yury Person ORCID (1), Mathias Schacht ORCID (2) (3)
(1) Institut für Mathematik [Berlin]
(2) Fachbereich Mathematik [Hamburg]
(3) Fachbereich Mathematik = Department of Mathematics [Hamburg]
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).
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree

    Lecture notes in computer science

    Authors : Edyta Szymańska

    Journal reference : Volume , 2010, pp. 304-314

    DOI : 10.1007/978-3-642-16926-7_28
Preview
Loading PDF preview...