networkx.algorithms.approximation.dominating_set.min_edge_dominating_set¶
-
min_edge_dominating_set
(G)[source]¶ Returns minimum cardinality edge dominating set.
- Parameters
G (NetworkX graph) – Undirected graph
- Returns
min_edge_dominating_set – Returns a set of dominating edges whose size is no more than 2 * OPT.
- Return type
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|)\).