min_edge_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 – Returns a set of dominating edges whose size is no more than 2 * OPT. Return type: set 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
.