maximum_independent_set(G)
Independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I. The size of an independent set is the number of vertices it contains .
A maximum independent set is a largest independent set for a given graph G and its size is denoted $\alpha(G)$. The problem of finding such a set is called the maximum independent set problem and is an NP-hard optimization problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.
The Independent Set algorithm is based on .
Finds the $O(
<SubstitutionRef: |value: '|V|' |>/(log|V|)^2)$ apx of independent set in the worst case.
Undirected graph
If the graph is directed or is a multigraph.
The apx-maximum independent set
Returns an approximate maximum independent set.
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them