Its already past 5 o'clock in the morning and im still in front of this computer. I'm still workin on my project. I think i finished about 20 % of it this morning. I really need some sleep.
anyway here's a recap of what i was able to finish within the past 2 weeks of workin on the Vertex connectivity problem.
Anyway since I am not obliged to create my own algorithm, I try to find algorithms and code pieces which I could incorporate/use to finish this project. Well i do have an algorithm(i think). Anyway it's a bruteforce approach to solving this problem. Here are the stages, I think i have researched enough so I can now explain the process i'll have to take to solve this problem.
the first few steps have been finished already:
1. Find the edge connectivity: How do I do this?
Not so simple but (thank you!) I was able to implement it already.
this is based on Menger's theorem. The maximum-flow-minimum-cut theorem. I will not be discussing the details of theorem. Here's an application. But first, here's what we will need to know.
what is a maximum flow? It is simply described as the maximum flow one can send from a source vertex s to a sink vertex t. What is it's connection to edge connectivity? simple... based on Menger's theorem..(in lay man's term) When you set all the edges' capacity to 1 and find the Maximum flow from source s to t, the Maximum flow is also the edge connectivity of s and t or the minimum no. of edges you need to remove for s and t to be disconnected.
this is based on Menger's theorem. The maximum-flow-minimum-cut theorem. I will not be discussing the details of theorem. Here's an application. But first, here's what we will need to know.
what is a maximum flow? It is simply described as the maximum flow one can send from a source vertex s to a sink vertex t. What is it's connection to edge connectivity? simple... based on Menger's theorem..(in lay man's term) When you set all the edges' capacity to 1 and find the Maximum flow from source s to t, the Maximum flow is also the edge connectivity of s and t or the minimum no. of edges you need to remove for s and t to be disconnected.
2. Now I have the edge connectivity, what will i need this for?
I already thought of that. Actually the edge connectivity algorithm can be reduced/altered to be a vertex connectivity algorithm.
3. Now what?We can now use this algorithm to find the global vertex connectivity of the graph! how you ask? simple! Get the vertex connectivity for all s and t. The result with the minimum vertex connectivity value will be the global vertex connectivity..
For now I was only able to Implement the edge connectivity algorithm. Tonight I will be working on the vertex connectivity algorithm, Ive already finished the combination algorithm so finding all combinations of s and t is already considered finished. After finishing i will be adding some optimization for the algorithms. I have already thought of one. You wanna hear? I wouldn't have to test all combinations of vertices for connectivity... only those vertices which are non djacent! yeba! Thats all for now. I feel kinda sleepy already!
a
For now I was only able to Implement the edge connectivity algorithm. Tonight I will be working on the vertex connectivity algorithm, Ive already finished the combination algorithm so finding all combinations of s and t is already considered finished. After finishing i will be adding some optimization for the algorithms. I have already thought of one. You wanna hear? I wouldn't have to test all combinations of vertices for connectivity... only those vertices which are non djacent! yeba! Thats all for now. I feel kinda sleepy already!
a
