TY - JOUR

T1 - Maximum independent set approximation based on Bellman-Ford algorithm

AU - Dahshan, Mostafa H.

PY - 2014/10/1

Y1 - 2014/10/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Combinatorial problems

KW - Graph algorithms

KW - Maximum independent set

UR - http://www.scopus.com/inward/record.url?scp=84907688447&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84907688447&partnerID=8YFLogxK

U2 - 10.1007/s13369-014-1159-7

DO - 10.1007/s13369-014-1159-7

M3 - Article

AN - SCOPUS:84907688447

VL - 39

SP - 7003

EP - 7011

JO - Arabian Journal for Science and Engineering

JF - Arabian Journal for Science and Engineering

SN - 2191-4281

IS - 10

ER -