Maximum independent set approximation based on Bellman-Ford algorithm

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


This paper presents a new algorithm for approximating the solution of the maximum independent set (MIS) problem. The proposed algorithm takes a novel approach of treating the MIS problem as a least-cost path problem, using an adapted version of Bellman–Ford algorithm, in which all vertices are used as sources, and the cost of a vertex is measured as the number of vertices excluded if this vertex is included in the independent set. Analysis of the proposed algorithm shows that its running time is approximately O(n(n2−m)), where n is the number of vertices and m is the number of edges. Extensive tests against several benchmark graphs and random-generated graphs show a significant improvement of the proposed algorithm over other approximation algorithms, including one of the best known ones such as Greedy algorithm.

Original languageEnglish
Pages (from-to)7003-7011
Number of pages9
JournalArabian Journal for Science and Engineering
Issue number10
Early online date31 May 2014
Publication statusPublished - 01 Oct 2014


Dive into the research topics of 'Maximum independent set approximation based on Bellman-Ford algorithm'. Together they form a unique fingerprint.

Cite this