On approximating minimum vertex cover for graphs with perfect matching (Q557830)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On approximating minimum vertex cover for graphs with perfect matching |
scientific article |
Statements
On approximating minimum vertex cover for graphs with perfect matching (English)
0 references
30 June 2005
0 references
Given a graph \(G\) the minimum vertex cover problem asks to find a minimum cardinality subset of vertices covering all edges of \(G\). The authors show that the problem is not easier for general graphs with perfect matching. For sparse graphs with perfect matching of average degree 5 they have given a 1.414-approximation algorithm. They note that an improvement of their results was given by \textit{M. Chlebík} and \textit{J. Chlebíková} [Lecture Notes in Computer Science 3153, 263--273 (2004; Zbl 1096.68061)].
0 references
minimum vertex cover
0 references
graph matching
0 references
approximation algorithm
0 references
inapproximability
0 references
