Maximum independent set approximation based on Bellman-Ford algorithm

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

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
Volume39
Issue number10
Early online date31 May 2014
DOIs
Publication statusPublished - 01 Oct 2014

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

Cite this