Inapproximability ratios for crossing number

DOI10.1016/j.endm.2017.10.021zbMath1383.05150OpenAlexW2765475555MaRDI QIDQ2413159

Rafael Veiga Pocai

Publication date: 9 April 2018

Full work available at URL: https://doi.org/10.1016/j.endm.2017.10.021

zbMATH Keywords

computational complexityapproximationcrossing numberinapproximability

Mathematics Subject Classification ID

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?

This page was built for publication: Inapproximability ratios for crossing number