[Lemon-user] k-node-connectivity

[Balázs Dezső]

>> 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.
I think, this algorithm is not complete. This can be done for edge
connectivity, but it's not suitable for node connectivity. This
algorithm does not cover the case when s is part of the cut nodes. The
algorithm 11 does almost the same, but it also takes all adjacent
nodes of s, and calculates the cut between each node pairs. If the
node s is not part of every minimum cut of the graph, then the
suggested algorithm finds the minimum cut. Otherwise, node s has two
neighbors which are on the two sides of the cut, so the second
iteration finds the cut. If you implement this algorithm, s should be
chosen with the smallest degree.

Other solution to use at least K+1 source nodes to compute the minimum
cut from and to, where K is the global minimum cut. Then you can be
sure, that at least of the source nodes was not part of all minimum
cuts. Because K is not known at the beginning of the algorithm,
therefore you can start with a large estimation, and adjust the value
when a new cut is found. It is in Algorithm 10.

Balazs


On Wed, Apr 4, 2012 at 12:43 PM, Martin <bauerhorst0815 at googlemail.com> wrote:
> 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
>>>
>