Re: Vertex cut sets

We do have an interface and a patch, written in C, to on-metis which obtains 
k-way graph partitioning by vertex separators (GPVS). Please be informed that, 
on-metis does not handle weighted vertices. 

We have a local GPVS code, also in C, that handles weighted vertices.
However, it does not perform as good as on-metis for unweighted vertices.



Cevdet Aykanat
Computer Engineering Department
Bilkent University
06800 Ankara, Turkey
URL  : http://www.cs.bilkent.edu.tr/~aykanat/

> 
> Most partitioning algorithms, for example spectral orderings, give edge
> cut sets but what we often want (and indeed Jennifer Scott and I need
> in a present study) is a vertex cut set.  Although getting such a set
> is trivial, I believe that getting a low cardinality set is not ??
> 
> Does anyone have or know of a code (preferably Fortran :-)) for doing a
> reasonable job on this.  We know there must be such algorithms buried within 
> codes like MeTiS but there does not appear to be a separate interface for
> this task.
> 
> Thank you for any help on this
> 
> Iain Duff