## Mercurial > repos > shellac > sam_consensus_v3

### comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/independent_set.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

author | shellac |
---|---|

date | Mon, 22 Mar 2021 18:12:50 +0000 |

parents | |

children |

comparison

equal
deleted
inserted
replaced

-1:000000000000 | 0:4f3585e2f14b |
---|---|

1 r""" | |

2 Independent Set | |

3 | |

4 Independent set or stable set is a set of vertices in a graph, no two of | |

5 which are adjacent. That is, it is a set I of vertices such that for every | |

6 two vertices in I, there is no edge connecting the two. Equivalently, each | |

7 edge in the graph has at most one endpoint in I. The size of an independent | |

8 set is the number of vertices it contains. | |

9 | |

10 A maximum independent set is a largest independent set for a given graph G | |

11 and its size is denoted $\alpha(G)$. The problem of finding such a set is called | |

12 the maximum independent set problem and is an NP-hard optimization problem. | |

13 As such, it is unlikely that there exists an efficient algorithm for finding | |

14 a maximum independent set of a graph. | |

15 | |

16 `Wikipedia: Independent set <https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>`_ | |

17 | |

18 Independent set algorithm is based on the following paper: | |

19 | |

20 $O(|V|/(log|V|)^2)$ apx of maximum clique/independent set. | |

21 | |

22 Boppana, R., & Halldórsson, M. M. (1992). | |

23 Approximating maximum independent sets by excluding subgraphs. | |

24 BIT Numerical Mathematics, 32(2), 180–196. Springer. | |

25 doi:10.1007/BF01994876 | |

26 | |

27 """ | |

28 from networkx.algorithms.approximation import clique_removal | |

29 | |

30 __all__ = ["maximum_independent_set"] | |

31 | |

32 | |

33 def maximum_independent_set(G): | |

34 """Returns an approximate maximum independent set. | |

35 | |

36 Parameters | |

37 ---------- | |

38 G : NetworkX graph | |

39 Undirected graph | |

40 | |

41 Returns | |

42 ------- | |

43 iset : Set | |

44 The apx-maximum independent set | |

45 | |

46 Notes | |

47 ----- | |

48 Finds the $O(|V|/(log|V|)^2)$ apx of independent set in the worst case. | |

49 | |

50 | |

51 References | |

52 ---------- | |

53 .. [1] Boppana, R., & Halldórsson, M. M. (1992). | |

54 Approximating maximum independent sets by excluding subgraphs. | |

55 BIT Numerical Mathematics, 32(2), 180–196. Springer. | |

56 """ | |

57 iset, _ = clique_removal(G) | |

58 return iset |