Warning

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

min_edge_dominating_set

min_edge_dominating_set(G)

Return minimum cardinality edge dominating set.

Parameters:

G : NetworkX graph

Undirected graph

Returns:

min_edge_dominating_set : set

Returns a set of dominating edges whose size is no more than 2 * OPT.

Notes

The algorithm computes an approximate solution to the edge dominating set problem. The result is no more than 2 * OPT in terms of size of the set. Runtime of the algorithm is \(O(|E|)\).