Ramsey numbers and an approximation algorithm for the vertex cover problem
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3853131 (Why is no real title available?)
- scientific article; zbMATH DE number 3675940 (Why is no real title available?)
- scientific article; zbMATH DE number 3688740 (Why is no real title available?)
- A note on Ramsey numbers
- Efficient bounds for the stable set, vertex cover and set packing problems
- Graph Theory and Probability
- Lower bounds on the independence number in terms of the degrees
- Some graph theoretic results associated with Ramsey's theorem
- The complexity of determining a shortest cycle of even length
- Vertex packings: Structural properties and algorithms
Cited in
(43)- Vertex cover in conflict graphs
- Graph covering using bounded size subgraphs
- scientific article; zbMATH DE number 7651162 (Why is no real title available?)
- Approximating minimum feedback vertex sets in hypergraphs
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- A primal-dual approximation algorithm for \textsc{minsat}
- Minimum vertex cover in rectangle graphs
- A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation
- Improved Upper Bounds for Partial Vertex Cover
- Approximating maximum independent sets by excluding subgraphs
- Disjointness graphs of short polygonal chains
- Approximating maximum independent sets by excluding subgraphs
- PTAS for connected vertex cover in unit disk graphs
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- On approximating minimum vertex cover for graphs with perfect matching
- A unified approximation algorithm for node-deletion problems
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Randomized approximation of the stable marriage problem
- Heuristic methods and applications: A categorized survey
- Computing independent sets in graphs with large girth
- A 2-approximation NC algorithm for connected vertex cover and tree cover
- Randomized greedy algorithms for independent sets and matchings in regular graphs: exact results and finite girth corrections
- The power of amortized recourse for online graph problems
- scientific article; zbMATH DE number 7650095 (Why is no real title available?)
- A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
- Approximating the tree and tour covers of a graph
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- A primal-dual approach to approximation of node-deletion problems for matroidal properties
- Strong and weak edges of a graph and linkages with the vertex cover problem
- Reoptimization of Weighted Graph and Covering Problems
- scientific article; zbMATH DE number 3959477 (Why is no real title available?)
- Approximating the dense set-cover problem
- Approximation for vertex cover in -conflict graphs
- The maximum clique problem in multiple interval graphs
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- Minimum vertex cover in ball graphs through local search
- A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach
- Iterative improvement of vertex covers
- A simple LP-free approximation algorithm for the minimum weight vertex cover problem
This page was built for publication: Ramsey numbers and an approximation algorithm for the vertex cover problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q762496)
