Loading...
Please wait, while we are loading the content...
Similar Documents
An Approximation of the Minimum Vertex Cover in a Graph (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Nagamochi, Hiroshi Ibaraki, Toshihide |
| Abstract | For a given undirected graph G with n vertices and m edges, we present an approximation algorithm for the minimum vertex cover problem. Our algorithm nds a vertex cover within 2 8m 13n 2 +8m of the optimal size in O(nm) time. Key words: graph, vertex cover, matching, cycle, approximation algorithm 1 Introduction A vertex cover of a graph G is a subset of vertices such that every edge e 2 E is incident to a vertex in the subset. The Vertex Cover Problem (VCP) asks to nd a vertex cover having the smallest number of vertices in a given graph. The problem is one of the classical combinatorial optimization problems on graphs. It, however, is known to be NP-complete [7], even if a given graph G is planar [3], and APX-complete [8] even if the degree of G is bounded by a constant d. Let G = (V; E) stand for a simple undirected graph with a vertex set V and an edge set E, and let n = jV j and m = jEj. One can easily see that, given a maximal matching M E on G, the set of end vertic... |
| File Format | |
| Volume Number | 16 |
| Journal | Japan J. Indust. Appl. Math |
| Language | English |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Minimum Vertex Cover Vertex Cover Undirected Graph Vertex Cover Problem Classical Combinatorial Optimization Problem End Vertic Key Word Maximal Matching Minimum Vertex Cover Problem Optimal Size Simple Undirected Graph Approximation Algorithm Edge Set Introduction Vertex Cover |
| Content Type | Text |
| Resource Type | Article |
