Hardness of approximation for crossing number
classification
💻 cs.CG
cs.CCmath.CO
keywords
crossingnumbertherealgorithmapproximationc-approximationconstanteven
read the original abstract
We show that, if P\not=NP, there is a constant c > 1 such that there is no c-approximation algorithm for the crossing number, even when restricted to 3-regular graphs.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.