Re: Vertex cut sets

Iain -- Chaco supports this operation with a fairly simple (albeit 
undocumented)
interface.  The current implementation has some limitations - specifically,
it only partitions into two sets, and it requires the graph to be connected.
But despite these shortcomings, it has been employed in several sparse
reordering tools.

- Bruce



At 09:05 AM 3/13/2003 +0000, Iain Duff wrote:

>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
>_______________________________________________
>Csc mailing list
>Csc-lVPF2Jp+hdv2fBVCVOL8/[email protected]
>http://list.odu.edu/listinfo/csc