Function ADS::vertexCoverApprox

• Defined in File Approximation.h

Function Documentation

inline Nodes ADS::vertexCoverApprox(const Adjacency &G)

both ends of each edge [ u , v ], u < v, whose ends are both out of S, at most twice a minimum vertex cover; O( n^2 ) on the adjacency matrix

Pre:

G is unoriented, i.e., square and symmetric

Post:

a cover of the edges