Given a weighted connected component, what is the weight of of the maximum independent set, and how many different sets have this weight? A Petersen graph GP(5, 2) with zero vertex weights has three maximal subsets by size, 0 maximum set weight but 76 distinct independent sets with this weight. Continue reading

# Maximum weighted independent set – connected component

**09**
*Friday*
Dec 2016

Posted Algorithms, BitSet, Graph Theory, Independent sets, cliques, colors, Java, Mathematics

in