Inapproximability ratios for crossing number
From MaRDI portal
Publication:2413159
DOI10.1016/j.endm.2017.10.021zbMath1383.05150OpenAlexW2765475555MaRDI QIDQ2413159
Publication date: 9 April 2018
Full work available at URL: https://doi.org/10.1016/j.endm.2017.10.021
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05C99) Signed and weighted graphs (05C22)
Cites Work
- Hardness of approximation for crossing number
- Crossing number is hard for cubic graphs
- Crossing Number is NP-Complete
- Handbook of Approximation Algorithms and Metaheuristics
- On the power of unique 2-prover 1-round games
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?