Algorithm to find 'maximal' indipendent set in a simple graph
- by none
Hi,
in words, can someone post directions towards finding the 'maximal' independent set in a simple graph?
I read up something from ETH site which said one can find such in O(n) by simply picking a random vertex v and than scanning the rest and attempting to find if there's an edge from v to the rest.
Thanks