tolerance factor for partition sizes
I am wondering if there is a way to tell metis (either through command line / lib call) to generate partitions of unequal sizes up to a certain tolerance factor, similar to ubfactor in hmetis? I have looked into ubvec for mCPartGraphKway but since my graph does not have multiple constraints that does not apply. Thanks!
Submitted by akc on Mon, 2010-09-20 20:10
»
- Login to post comments
RE: There is no way to do that
There is no way to do that from the API. However, you can use the mCPartGraphKway routine for a single constraint problem. Just make your two constraints to have identical vertex weights.
RE: Can you please elaborate on
Can you please elaborate on what you meant by "make two constraints to have identical vertex weights"? The problem is a single constraint one. Thanks!
RE: A graph G(V,E) in which each
A graph G(V,E) in which each vertex has a weight w(v), can be used to derive a two-constraint graph in which each vertex has a weight vector of (w(v), w(v)). Now a partitioning of this two-constraint graph that satisfies the specifies balance constraints will also be a partitioning of the original graph (with the same balancing constraints).
In this way, you can take your single constraint problem, derive a two-constraint problem, partition it using the multi-constraint routines, and you are done.