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

DOI10.1016/J.DAM.2011.10.027zbMATH Open1237.05200OpenAlexW2038655901MaRDI QIDQ765356FDOQ765356

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 algorithmvertex cover problemNP-complete problemsLP-relaxationweak edge reduction

Mathematics Subject Classification ID

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

Cites Work

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

   Recommendations

• On strong (weak) independent sets and vertex coverings of a graph 👍 👎
• Covering problems in edge- and node-weighted graphs 👍 👎
• Covering problems in edge- and node-weighted graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Edge dominating sets and vertex covers 👍 👎
• Title not available (Why is that?) 👍 👎

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765356)