Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

min_weighted_vertex_cover

min_weighted_vertex_cover(G, weight=None)[source]

2-OPT Local Ratio for Minimum Weighted Vertex Cover

Find an approximate minimum weighted vertex cover of a graph.

Parameters:
  • G (NetworkX graph) – Undirected graph
  • weight (None or string, optional (default = None)) – If None, every edge has weight/distance/cost 1. If a string, use this edge attribute as the edge weight. Any edge attribute not present defaults to 1.
Returns:

min_weighted_cover – Returns a set of vertices whose weight sum is no more than 2 * OPT.
Return type:

set

Notes

Local-Ratio algorithm for computing an approximate vertex cover. Algorithm greedily reduces the costs over edges and iteratively builds a cover. Worst-case runtime is \(O(|E|)\).

References

[1]Bar-Yehuda, R., & Even, S. (1985). A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25, 27–46 http://www.cs.technion.ac.il/~reuven/PDF/vc_lr.pdf