This page is documentation for a DEVELOPMENT / PRE-RELEASE version. Switch to stable version

NetworkX User Survey 2023 🎉 Fill out the survey to tell us about your ideas, complaints, praises of NetworkX!

min_edge_dominating_set#

min_edge_dominating_set(G)[source]#

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.

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