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

DOI10.1016/J.DAM.2011.10.027MaRDI QIDQ765356zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 2119717 (Why is no real title available?)
• A better approximation ratio for the vertex cover problem
• An edge-reduction algorithm for the vertex cover problem
• Experimental and Efficient Algorithms
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• On the hardness of approximating minimum vertex cover
• On the power of unique 2-prover 1-round games
• Properties of vertex packing and independence system polyhedra
• Proving integrality gaps without knowing the linear program
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Some optimal inapproximability results
• The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
• Vertex Cover Approximations on Random Graphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex packings: Structural properties and algorithms

Cited in

(3)

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

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)