An algorithm for finding a maximum weighted independent set in an arbitrary graph

We propose and implement an exact algorithm for the maximum weighted independent set problem based on an unconstrained quadratic 0–1 formulation and branch and bound techniques. The use of a non-greedy branch and bound method using depth first search is presented and justified along with various heuristics to improve performance. We also present computational results using randomly generated graphs with up to 500 vertices.