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

DOI10.1016/j.dam.2011.10.027zbMath1237.05200OpenAlexW2038655901MaRDI 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 algorithmNP-complete problemsvertex cover problemLP-relaxationweak edge reduction

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

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

This page was built for publication: Strong and weak edges of a graph and linkages with the vertex cover problem