Independent set and vertex cover algorithms
Procs
func isIndependentSet[N](g: Graph[N]; nodes: HashSet[N]): bool
- Check if the given node set is independent (no edges between them).
proc maximumIndependentSet[N](g: Graph[N]): HashSet[N]
- Greedy approximation for maximum independent set. Iteratively picks the node with minimum degree and removes it and neighbors.
proc minimumVertexCover[N](g: Graph[N]): HashSet[N]
- 2-approximation minimum vertex cover. Greedy: pick edges and add both endpoints until all edges covered.