Ramsey numbers and an approximation algorithm for the vertex cover problem
From MaRDI portal
Publication:762496
DOI10.1007/BF00290149zbMath0558.05044OpenAlexW2041605864MaRDI QIDQ762496
Ewald Speckenmeyer, Burkhard Monien
Publication date: 1985
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00290149
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Generalized Ramsey theory (05C55)
Related Items (41)
An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs ⋮ Randomized approximation of the stable marriage problem ⋮ Improved Upper Bounds for Partial Vertex Cover ⋮ A 2-approximation NC algorithm for connected vertex cover and tree cover ⋮ Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation ⋮ A primal-dual approximation algorithm for \textsc{minsat} ⋮ A primal-dual approach to approximation of node-deletion problems for matroidal properties ⋮ Approximation for vertex cover in \(\beta\)-conflict graphs ⋮ Vertex cover in conflict graphs ⋮ Graph covering using bounded size subgraphs ⋮ Disjointness graphs of short polygonal chains ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The power of amortized recourse for online graph problems ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ A \((2-c\frac{1}{\sqrt{N}})\)-approximation algorithm for the stable marriage problem ⋮ Computing independent sets in graphs with large girth ⋮ A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach ⋮ Iterative improvement of vertex covers ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ A simple LP-free approximation algorithm for the minimum weight vertex cover problem ⋮ Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections ⋮ Approximating maximum independent sets by excluding subgraphs ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ Minimum vertex cover in ball graphs through local search ⋮ Approximating the tree and tour covers of a graph ⋮ Approximating the dense set-cover problem ⋮ Minimum vertex cover in rectangle graphs ⋮ Polynomial approximation algorithms with performance guarantees: an introduction-by-example ⋮ On approximating minimum vertex cover for graphs with perfect matching ⋮ Hedging uncertainty: approximation algorithms for stochastic optimization problems ⋮ Approximating maximum independent sets by excluding subgraphs ⋮ Reoptimization of Weighted Graph and Covering Problems ⋮ A unified approximation algorithm for node-deletion problems ⋮ A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM ⋮ Heuristic methods and applications: A categorized survey ⋮ Strong and weak edges of a graph and linkages with the vertex cover problem ⋮ PTAS for connected vertex cover in unit disk graphs ⋮ Approximating minimum feedback vertex sets in hypergraphs ⋮ Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph ⋮ The maximum clique problem in multiple interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of determining a shortest cycle of even length
- Efficient bounds for the stable set, vertex cover and set packing problems
- A note on Ramsey numbers
- Lower bounds on the independence number in terms of the degrees
- Graph Theory and Probability
- Vertex packings: Structural properties and algorithms
- Some graph theoretic results associated with Ramsey's theorem
This page was built for publication: Ramsey numbers and an approximation algorithm for the vertex cover problem
