[Lemon-user] k-node-connectivity

[Attila Bernáth]

Hi Martin,

As far as I know, this is not implemented explicitly, but it is easy to get:
to determine graph edge-connectivity, use Nagamochi-Ibaraki,
to determine digraph arc-connectivity, use Hao-Orlin,

to determine the node-connectivities, you can only use the SplitNodes
adaptor (as Balázs also writes), but you need to calculate the
node-connectivity using a maxflow method for some pairs of nodes:

fix a node $s$
for every other node $t$, determine the node connectivity from $s$ to
$t$ using the SplitNodes adaptor, and a maxflow algorithm (and also
from $t$ to $s$): the minimum of these will be the node connectivity
of the (di)graph.

Attila

Ps: I can put together some example code, if you wish, for one of these.

Martin <bauerhorst0815 at googlemail.com> írta (2012. április 3. 22:02):
> 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
>