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

Abstract

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.

Keywords:

• Maximum weighted independent set
• branch and bound
• depth first search
• non-greedy approach
• computational results