Page 1 of 16 ALGORITHMIC ASPECTS OF TELECOMMUNICATION NETWORKS TE 6385 Project - 2 IMPLEMENTATION OF NAGAMOCHI – IBARAKI ALGORITHM Ashwin Wuluvarana Net Id: AVW130130 [email protected] Fall 2014Page 2 of 16 INTRODUCTION: Graph connectivity is one of the classical subjects in graph theory, and has many practical applications, for example, in chip and circuit design, reliability of communication networks, transportation planning, and cluster analysis. Finding the minimum cut of an undirected edge-weighted graph is a fundamental algorithmic problem. Precisely, it consists in finding a nontrivial partition of the graphs vertex set V into two parts such that the cut weight, the sum of the weights of the edges connecting the two parts, is minimum. The usual approach to solve this problem is to use its close relationship to the maximum flow problem. The famous Max-Flow-Min-Cut-Theorem by Ford and Fulkerson showed the duality of the maximum flow and the so-called minimum s-t-cut. There, s and t are two vertices that are the source and the sink in the flow problem and have to be separated by the cut, that is, they have to lie in different parts of the partition. Until recently all cut algorithms were essentially flow algorithms using this duality. Finding a minimum cut without specified vertices to be separated can be done by finding minimum s-t-cuts for a fixed vertex s and all |V| - 1 possible choices of V{s} and then selecting the lightest one . A cut, vertex cut, or separating set of a connected graph G is a set of vertices whose removal renders G disconnected. The connectivity or vertex connectivity (G) (where G is not a complete graph) is the size of a minimal vertex cut. A graph is called k-connected or k-vertex-connected if its vertex connectivity is k or greater. This means a graph G is said to be k-connected if there does not exist a set of k − 1 vertices whose removal disconnects the graph. A complete graph with n vertices, denoted Kn, has no vertex cuts at all, but by convention (Kn) = n − 1. A vertex cut for two vertices u and v is a set of vertices whose removal from the graph disconnects u and v. The local connectivity κ(u, v) is the size of a smallest vertex cut separating u and v. Local connectivity is symmetric for undirected graphs; that is, (u, v) = (v, u). Moreover, except for complete graphs, (G)equals the minimum of (u, v) over all nonadjacent pairs of vertices u, v.Page 3 of 16 SYNOPSIS: The theme of this project is to implement the Nagamochi- Ibaraki algorithm capable of finding a minimum cut in an undirected graph. OBJECTIVE: Using the given number of nodes and edges obtained by the randomly chosen values in the graph Implementation of the Nagamochi – Ibaraki Algorithm, explaining how it works and providing its pseudo code. Writing a computer program showing its implementation. Run the program on randomly generated examples. Consider the number of nodes to be fixed at n=20. Let m be the number of edges which vary between 40 and 400, increasing in steps of 5. Once a value of m is selected, the program creates a graph with n=20 nodes and m edges. Actual edges are selected randomly with parallel edges allowed and excluding self loops. Experiment with your random graph examples to find an experimental connection between the average degree of the graph and its edge- connectivity Lambda(G). Lambda(G ) is taken to be 0 if the graph happens to be disconnected. The connectivity depends on the average degree. The average degree in a graph characterizes the density of the graph, as it is expressible as d =2m/n, where m; n are the number of edges and nodes, respectively. The relationship between Lambda(G) as a function of the average degree d, while keeping n = 20 fixed is exhibited through a diagram. Let us call an edge critical, if its deletion decreases the connectivity. That is, an edge e is critical, if Lambda(G-e)< Lambda(G), where G-e denotes the graph G with edge e deleted. Let C(G) denote the number of critical edges in graph G. Using the random graphs generated above, show an experimental relationship between the number of critical edges and the average degree d of the graph. That is, show C(G) graphically as the function of d, while keeping n= 20 fixed. Also to construct a graph between Density of the network and value of k and how it changes with the parameter value k, for different values of k.Page 4 of 16 DESCRIPTION: Nagamochi-Ibaraki Algorithm is a simple deterministic algorithm discovered by Nagamochi and Ibaraki for finding minimum cuts of a graph G. Let the edge connectivity of a graph G be denoted by λ(G) and connectivity between two different nodes x and y be denoted by λ(x,y). Let Gxy be the graph obtained from G by merging the nodes x and y. In this operation we omit the possibly arising loop (if x, y were connected in G), but keep the parallel edges. We can now use the following result that is not hard to prove: For any two nodes x and y λ (G) =min{ λ (x,y) , λ (Gxy) } Thus, if we can find two nodes x,y for which λ (x,y) can be computed easily (without a flow computation), then the above formula yields a simple recursive algorithm. One can easily find such a pair of nodes. This is done via the Maximum Adjacency (MA) ordering. An MA ordering v1,....,vn of the nodes is generated recursively by the following algorithm:- Take any of the nodes for v1. Once v1,....,vn is already chosen, take a node for vi+1 that has the maximum number of edges connecting it with the set { v1,....,vn }. Nagamochi and Ibaraki proved that this ordering has the following nice property: Theorem: In any MA ordering v1,....,vn of the nodes λ (vn-1,vn)=d(vn) holds, where d(.) denotes the degree of the node. Therefore, it is enough to create an MA ordering, as described above, and take the last 2 nodes in this ordering for x, y. Then the connectivity between them will be equal to the degree of the last node in the MA ordering. Then one can apply the above formula recursively to get the minimum cut. Here we make use of the fact that it reduces the problem to computing λ (Gxy) and λ (Gxy) is already a smaller graph.Page 5 of 16 IMPLEMENTATION: Implementation – C language Graph Implementation – Excel The Implementation of the Nagamochi-Ibaraki Algorithm for
View Full Document