Determining the number of internal stability of a graph

Abstract

The number of internal stability or independence number of an undirected graph has many important applications. Computationally it belongs to the class of intractable problems known as NP-Hard. In this paper we develop a tree search algorithm to determine the ndependence number of an undirected graph. Extensive computational experience on 2400 randomly generated graphs ranging from 20% to 90% densities and from 50 to 200 vertice has shown that the proposed algorithm is very effective.

Keywords:

• Undirected graphs
• number of internal stability
• NP-Hard

C.R. Categories:

• 5.23