A heuristic algorithm to find rupture degree in graphs

Abstract

Since the problem of Konigsberg bridge was released in 1735, there have been many applications ofgraph theory in mathematics, physics, biology, computer science, and several fields of engineering. In particular, allcommunication networks can be modeled by graphs. The vulnerability is a concept that represents the reluctance of anetwork to disruptions in communication after a deterioration of some processors or communication links. Furthermore,the vulnerability values can be computed with many graph theoretical parameters. The rupture degree r(G) of a graphG = (V, E) is an important graph vulnerability parameter and defined as r(G) = max{ω(G − S) − |S| − m(G − S) :ω(G − S) ≥ 2, S ⊂ V }, where ω(G − S) and m(G − S) denote the number of connected components and the size of thelargest connected component in the graph G − S , respectively. Recently, it has been proved that finding the rupturedegree problem is NP -complete. In this paper, a heuristic algorithm to determine the rupture degree of a graph has beendeveloped. Extensive computational experience on 88 randomly generated graphs ranging from 20% to 90% densitiesand from 100 to 200 vertices shows that the proposed algorithm is very effective.