An algorithm for the maximum internally stable set in a weighted graph

Abstract

The problem of determining a maximum internally stable set in a weighted undirected graph belongs to the class of computationally intractable problems known as NP-hard. Furthermore it has a variety of many interesting applications. In this paper we develop a recursive backtracking algorithm to find a maximum internally stable set of a weighted undirected graph. Computational experience on more than 1500 randomly generated graphs ranging from 100 to 250 vertices and from 15% to 80%, densities has shown that the proposed algorithm is very effective.

Keywords:

• Weighted undirected graph
• maximum internally stable set
• NP-hard
• recursive backtracking algorithm

C.R. Categories::

• 5.32