On approximating minimum vertex cover for graphs with perfect matching (Q557830)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2184058
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On approximating minimum vertex cover for graphs with perfect matching |
scientific article; zbMATH DE number 2184058 |
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
0 references
0.95548356
0 references
0.93312705
0 references
0 references
0 references
0.9191861
0 references
0.9190191
0 references
