Strong and weak edges of a graph and linkages with the vertex cover problem

DOI10.1016/j.dam.2011.10.027zbMath1237.05200MaRDI QIDQ765356

Abraham P. Punnen, Qiaoming Han

Publication date: 19 March 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.027

zbMATH Keywords

approximation algorithm; NP-complete problems; vertex cover problem; LP-relaxation; weak edge reduction

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• On the hardness of approximating minimum vertex cover
• An edge-reduction algorithm for the vertex cover problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• A better approximation ratio for the vertex cover problem
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• On the power of unique 2-prover 1-round games
• Vertex packings: Structural properties and algorithms
• The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
• Properties of vertex packing and independence system polyhedra
• Vertex Cover Approximations on Random Graphs
• Some optimal inapproximability results
• Experimental and Efficient Algorithms