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

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

Authors: Qiaoming Han, Abraham P. Punnen 

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

Recommendations

• On strong (weak) independent sets and vertex coverings of a graph
• scientific article; zbMATH DE number 6161501
• On total vertex covers and edge domination in graphs
• scientific article; zbMATH DE number 1289751
• scientific article; zbMATH DE number 7250383
• scientific article; zbMATH DE number 861353
• Edge dominating sets and vertex covers
• scientific article; zbMATH DE number 2170477

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
• Proving integrality gaps without knowing the linear program
• 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

Cited In (3)

• Approximating the minimum weight weak vertex cover
• On the approximability of the vertex cover and related problems
• An edge-reduction algorithm for the vertex cover problem

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)