2

I'm in need of implementing the algorithm to actually locate the minimal vertex separators set of the whole graph (not just s-t).

It is my understanding that this can be done by doing the s-t procedure for all possible vertex pairs and then looking at the minimal sets of vertex independent paths that arise from that.

Now, I get that all possible paths can be found easily by solving "max flow" s-t, and I do it with matlab, but I'm curious about getting the maximally vertex independent sets of paths.

I understand, from this that this can be acheived by doubling the vertices in some way, but I'm not able to figure it out on my own.

Question covering a similar issue: I'm specifically interested in case (a) that the first comment termed "network flow". Practical algorithms for the disjoint paths problem

Any advice ?

PS: this is not homework. I'm actually trying to solve this problem on my data and I'm not a computer science expert.

Community
  • 1
cladelpino
  • 171
  • 5
  • Possible related question: http://cstheory.stackexchange.com/questions/2877/minimum-cut-through-vertices-nodes-not-edges – adrianN Aug 01 '16 at 10:39
  • Can the answer in that question that points to separating the incoming and outcoming edges (which is relevant to directed graphs) be extended to undirected ones by replacing each edge of the original graphs with two opposite directed ones ? – cladelpino Aug 01 '16 at 12:11

0 Answers0