Expand description
Independent set algorithms (ALGO-VC-002).
An independent set is a set of vertices such that no two vertices in the set are adjacent. Finding a maximum independent set is NP-hard; we provide a greedy heuristic.
The greedy algorithm repeatedly picks the vertex with minimum degree (among remaining vertices), adds it to the independent set, and removes it and all its neighbors from the candidate pool.
Functionsยง
- maximum_
independent_ set - Compute an approximate maximum independent set using a greedy heuristic.