IJCSE-V2I5P2

Please download to get full document.

View again

of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Categories
Published
International Scientific and Research Group
   International Journal of Computer science engineering Techniques-– Volume 2 Issue 5, July - Aug 20! ISSN: 2455-135X http://www.ijcsejournal.org  Page 7 A Heuristic Approach for the Independent Set Problem   Omar Kettani*, *(Scientific Institute, Physics of the Earth Laboratory/Mohamed V- University, Rabat) INTRODUCTION   In graph theory, the stable set (or maximum independent set) of a graph is a maximum cardinality subset of vertices in which no two vertices are adjacent. This problem which has many applications in computer science and operations research is computationally intractable in general [5] but can be solved in polynomial time on some special graph classes, like bipartite graphs [8], chair-free graphs [3] or claw-free graphs [7] [11]. Therefore, for large and hard instances one must design heuristic approaches to obtain near optimal solutions within reasonable time. Given an undirected graph G = (V, E) with vertex set V = V (G) of cardinality |V (G)| = n, and edge set E = E(G) of cardinality |E(G)| = m. The neighborhood of a vertex v ∈ V is the set N(v) = {u ∈ ∈ V: vu E} . A set S ⊆ V (G) is independent if no two vertices from S are adjacent; by Ind(G) we mean the set of all the independent sets of G. An independent set of maximum size will be referred to a maximum stable set of G. A vertex cover is a subset Vc ⊆ V , such that every edge in G has at least one endpoint in Vc. The rest of this paper is organized as follows: In section 2 we describe the proposed approach, whereas section 3 provides some examples of the application of the proposed heuristic on some famous graphs taken from the literature. Finally, concluding remarks are given in section 4.   P ROPOSED APPROACH   The main idea of the proposed heuristic is to build a maximal stable set I   by considering incrementally a minimal vertex cover Vc. Abstract: Given a graph G =(V, E), the independent set problem is to find a maximum cardinality subset S of V such that all vertices in S are pairwise non-adjacent. This problem is NP-hard in general but can be solved in polynomial time on some special graph classes, like bipartite graphs, chair-free graphs or claw-free graphs. In this article, we propose a heuristic algorithm for this problem. The results of its application on some famous graphs taken from the literature, with known optimal solutions demonstrates that this approach is effective.     RESEARCH ARTICLE OPEN ACCESS   International Journal of Computer science engineering Techniques-– Volume 2 Issue 5, July - Aug 20! ISSN: 2455-135X http://www.ijcsejournal.org  Page 8 The pseudo-code of the proposed heuristic algorithm is given below. Input: G(V, E) Output: A stable set I of G. J ←   [1,n] I ←  []  for i=1:n J1 ←  {j ∈  J/ a(j,1)=i} J2 ←  {j ∈  J/ a(j,2)=i} c ←{ a(J1,1) }   ∪{ a(J1,2) } v(i) ← c L(i) ←| c |  end for i1 ← ArgMin(L(i)) i ∈ J Vc ← v(i1) I(1) ←{ i1 } Κ ← J-(I ∪ Vc) while K ≠∅  do w ←  [] L ←  [] for i=1:n w(i) ←  v(i) ∪ Vc  if i ∈ K L(i) ←| w (i) | else   L(i) ← n+ 1 end end for i1 ← ArgMin(L(i)) i ∈ J I ←Ι ∪ { i1 }  Vc ← w( i1)   Κ ← J-(I ∪ Vc) end while output I 3. Some examples  In the following examples, we demonstrates the application of the proposed heuristic on some instance of famous graphs defined by their adjacency matrix. We report, the outputs of the heuristic as a list of the maximal stable sets S v  that contain vertex v (v=1,...,n), the independence number α  of G and the stable set S of G. (The vertices of S=I are colored in white in the following figures) fig.1 The graph of the Cube α =4 S={ 1 , 3 , 5 , 7 }   fig.2 the Icosahedron graph [10] α =3 S= { 1 , 4 , 11 } Fig. 1 A sample line graph using colors which contrast well both on screen and on a black-and-white hardcopy   International Journal of Computer science engineering Techniques-– Volume 2 Issue 5, July - Aug 20! ISSN: 2455-135X http://www.ijcsejournal.org  Page 9 fig.3 The graph K3,3 [6] α =3 S= { 1 , 2 , 3 } fig.4 The Dodecahedron graph [10] α =8 S={ 1 , 3 , 6 , 8 , 11 , 13 , 16 , 18 } fig.5 The Folkman graph [4] α =10 S= { 1 , 10 , 2 , 9 , 3 , 8 , 4 , 5 , 6 , 7 }   fig.6 The Petersen graph [9] α =4 S={ 1 , 3 , 6 , 10 } fig.7 The Thomassen graph [12] α =14 S= { 1 , 2 , 15 , 8 , 13 , 9 , 17 , 19 , 29 , 25 , 21 , 32 , 24 , 33 } fig.9 The Bondy-Murty graph G4 [2] α =9 S={ 1 , 3 , 4 , 5 , 12 , 14 , 16 , 9 , 2 }     International Journal of Computer science engineering Techniques-– Volume 2 Issue 5, July - Aug 20! ISSN: 2455-135X http://www.ijcsejournal.org  Page 10 f  ig.8 The Bondy-Murty graph G1 [2]   α =3 S={ 4 , 5 , 6 } fig.9 The Bondy-Murty graph G2 [2] α =4 S={3 , 5 , 8,10 } fig.10:The Bondy-Murty graph G3 [2] α =7 S={ 1,3 ,7 ,13 ,5 , 9 ,11 }   fig.11:The Grötzsch graph [15] α =5 S={ 2, 3 , 4 , 5 , 6} fig.12:The Herschel graph [16] α =6 S={2 , 4 , 9, 5 , 7 , 11}   fig.13:The Tutte-Coxeter graph [17]
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks