The input for a cellular manufacturing problem consists of a set X of m machines, a set Y of p
parts and an m× p matrix A=(aij), where aij= 1 or 0 according as the part pj is processed on
the machine m i. This data can be represented as a bipartite graph with bipartition X, Y
where mi is joined to pj if aij= 1. Given a partition π of V (G) into k subsets V 1, V 2,..., V k
such that| V i|≥ 2 and the induced subgraph< V> is connected, any edge of G with one end
in V i and other end in V j with i≠ j, is called an exceptional edges. The cellular …