[Lemon-user] k-node-connectivity

[Attila Bernáth]

Damn, Balázs is right. I was almost sending the wrong code.

Attila

Balázs Dezső <deba.mf at gmail.com> írta (2012. április 4. 15:01):
>>> 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
>>>>
>>
>