A 1.9999-approximation algorithm for vertex cover on string graphs
From MaRDI portal
Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Cites work
- A 2k-kernelization algorithm for vertex cover based on crown decomposition
- A 3-approximation algorithm for maximum independent set of rectangles
- A framework for approximation schemes on disk graphs
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Approximating maximum independent set for rectangles in the plane
- Approximation algorithms for maximum independent set of pseudo-disks
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation algorithms for polynomial-expansion and low-density graphs
- Approximation schemes for independent set and sparse subsets of polygons
- Bidimensionality: new connections between FPT algorithms and PTASs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
- Computing the independence number of intersection graphs
- Crown reductions for the minimum weighted vertex cover problem
- Excluded grid minors and efficient polynomial-time approximation schemes
- Excluded minors, network decomposition, and multicommodity flow
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Local tree-width, excluded minors, and approximation algorithms
- Minimum vertex cover in rectangle graphs
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Reducibility among combinatorial problems
- Separators in region intersection graphs
- String graphs requiring exponential representations
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Vertex packings: Structural properties and algorithms
Cited in
(2)
This page was built for publication: A 1.9999-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 Q6895826)
