Ramsey numbers and an approximation algorithm for the vertex cover problem
From MaRDI portal
Publication:762496
DOI10.1007/BF00290149zbMATH Open0558.05044OpenAlexW2041605864MaRDI QIDQ762496FDOQ762496
Authors: Burkhard Monien, Ewald Speckenmeyer 
Publication date: 1985
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00290149
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Graph Theory and Probability
- Lower bounds on the independence number in terms of the degrees
- The complexity of determining a shortest cycle of even length
- Vertex packings: Structural properties and algorithms
- A note on Ramsey numbers
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient bounds for the stable set, vertex cover and set packing problems
- Some graph theoretic results associated with Ramsey's theorem
Cited In (43)
- Title not available (Why is that?)
- Vertex cover in conflict graphs
- Approximating minimum feedback vertex sets in hypergraphs
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- A primal-dual approximation algorithm for \textsc{minsat}
- Improved Upper Bounds for Partial Vertex Cover
- A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem
- Minimum vertex cover in rectangle graphs
- Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation
- Disjointness graphs of short polygonal chains
- Approximating maximum independent sets by excluding subgraphs
- Approximating maximum independent sets by excluding subgraphs
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- PTAS for connected vertex cover in unit disk graphs
- On approximating minimum vertex cover for graphs with perfect matching
- A unified approximation algorithm for node-deletion problems
- Randomized approximation of the stable marriage problem
- Heuristic methods and applications: A categorized survey
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- 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
- Title not available (Why is that?)
- 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
- A primal-dual approach to approximation of node-deletion problems for matroidal properties
- Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
- Strong and weak edges of a graph and linkages with the vertex cover problem
- Reoptimization of Weighted Graph and Covering Problems
- Title not available (Why is that?)
- Approximating the dense set-cover problem
- Approximation for vertex cover in \(\beta\)-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
- Graph covering using bounded size subgraphs
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)
