7.1.5.2. networkx.algorithms.approximation.dominating_set.min_edge_dominating_set¶

networkx.algorithms.approximation.dominating_set.min_edge_dominating_set(G)[source]¶

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|).