[Lemon-user] k-node-connectivity

[Martin]

Hi,

thanks for your reply Balazs and Attila.

@Attila: If you like and have the time it would be quite helpful for me
to get some example code for the node connectivity (third issue of your
answer).

Thanks a lot in advance,
Martin

> 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
>>