min_edge_dominating_set

min_edge_dominating_set(G)

Returns minimum cardinality edge dominating set.

Parameters:

GNetworkX graph

Undirected graph

Returns:

min_edge_dominating_setset

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

Raises:

ValueError

If the input graph G is empty.

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

Examples

>>> G = nx.petersen_graph()
>>> nx.approximation.min_edge_dominating_set(G)
{(0, 1), (4, 9), (6, 8), (5, 7), (2, 3)}