Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/independent_set.py @ 0:4f3585e2f14b draft default tip
"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 |