[Lemon-user] k-node-connectivity

[Balázs Dezső]

Hi,

I think, there is no direct method to calculate k-node-connectivity in
LEMON, but the main building blocks are implemented:
In the lemon tutorial (adaptors section), there is an example, how can
you use SplitNodes adaptor together with a max flow algorithm to
compute s-t node connectivity.
http://lemon.cs.elte.hu/pub/tutorial/a00008.html

The following book contains a good introduction for node connectivity
algorithms.
http://www.cse.msu.edu/~esfahani/book_chapter/Graph_connectivity_chapter.pdf
Either algorithm 10 or algorithm 11 can be easily implemented using
the s-t connectivity algorithm as subroutine.

Balazs

On Tue, Apr 3, 2012 at 10:02 PM, Martin <bauerhorst0815 at googlemail.com> wrote:
> Hi,
>
> does anybody know a function to get the k-node-connectivity
> (k-vertex-connectivity) of a digraph (or graph)?
> (http://en.wikipedia.org/wiki/K-vertex-connected_graph)
> I could only find the function biNodeConnected to check whether a graph
> is 2-node-connected so far.
>
> Thanks,
> Martin
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user