# How can I partition a graph with two types of vertices?

I have a graph where the vertices represent latches and the edges represent whether there is a path from one latch to another (through combinational logic). The edges are undirected.

I would like to partition these latches into groups that tend to share neighbors. My problem is that there are two types of latches, positive and negative, and a group can only contain latches of the same type. Also, each latch can only be a member of one group.

Edges only exist between latches of different types.

Does METIS support what I'm trying to do? Could someone give me a little direction on how to accomplish this?

Thanks,

Matt

Submitted by mfojtik on Tue, 2010-04-27 07:13

»

- Login to post comments

## RE: Matt, This is an interesting

Matt,

This is an interesting problem. Here is an approach that you may want to explore.

Let A and B be the two types of latches that you have.

Since the edges connect only type A and type B vertices, create two graphs. The first

will contain the type A vertices only and the second will contain the type B vertices.

Two vertices (u,v) in A will be connected via an edge if there is a (u,x), (x,v) edge

where x is a vertex in B. Set the weight of that edge to the different x vertices that

satisfy the above condition. Use a similar approach for creating edges in the graph

that contains the B vertices. Then, go ahead and partition those two graphs independently

of each other.

george