An 11/6-approximation algorithm for vertex cover on string graphs
From MaRDI portal
Cites work
- A 1.9999-approximation algorithm for vertex cover on string graphs
- Algorithm Theory - SWAT 2004
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation schemes for independent set and sparse subsets of polygons
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- Colouring arcwise connected sets in the plane. I
- Colouring arcwise connected sets in the plane. II
- Graphen und Matrices.
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
- On independent sets, 2-to-2 games, and Grassmann graphs
- Properties of vertex packing and independence system polyhedra
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Reducibility among combinatorial problems
- Separators in region intersection graphs
- String graphs requiring exponential representations
- String graphs. II: Recognizing string graphs is NP-hard
- Towards a proof of the 2-to-1 games conjecture?
- Triangle-free geometric intersection graphs with no large independent sets
- Triangle-free intersection graphs of line segments with large chromatic number
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
This page was built for publication: An 11/6-approximation algorithm for vertex cover on string graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7312667)
