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

1 January 1991

journal article
research article
Published by Taylor & Francis in International Journal of Computer Mathematics

Vol. 38 (3) , 163-175
https://doi.org/10.1080/00207169108803967

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

This publication has 13 references indexed in Scilit:

Computational aspects of a branch and bound algorithm for quadratic zero-one programming
Computing, 1990
A global optimization approach for solving the maximum clique problem
International Journal of Computer Mathematics, 1990
Geometric Algorithms and Combinatorial Optimization
Published by Springer Nature ,1988
On the Maximum Weight Clique Problem
Mathematics of Operations Research, 1987
Finding a Maximum Clique in an Arbitrary Graph
SIAM Journal on Computing, 1986
Determining the number of internal stability of a graph
International Journal of Computer Mathematics, 1982
A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
Mathematical Programming, 1981
Clique detection for nondirected graphs: Two new algorithms
Computing, 1979
Algorithm 457: finding all cliques of an undirected graph
Communications of the ACM, 1973
Algorithms for a maximum clique and a maximum independent set of a circle graph
Networks, 1973