Decomposition algorithms for finding the shortest path between a source node and a sink node of a network

Decomposition algorithms for finding a shortest path between a source node and a sink node of an arbitrary distance network are developed. Different decomposition algorithms are proposed for different network topologies. Since Shier's algorithm compares very favorably with other decomposition algorithms in all the network topologies, we compare our algorithms against Shier's algorithm. It is shown that the efficiency of the proposed algorithms compares very favorably with Shier's algorithm. For special types of networks the computational requirements of the proposed algorithm is a polynomial of O(n²).     

Decomposition algorithms for minimal cut problems

Consider a network G(N. A) with n nodes, where node 1 designates its source node and node n designates its sink node. The cuts (Z_i, =), i= 1…, n - 1 are called one-node cuts if 1 ? Z_i,. n q Z_i, Z₁-_? {1}, Z_i ? Z_i+1 and Z_i and Z_i+l differ by only one node. It is shown that these one-node cuts decompose G into 1 m n/2 subnetworks with known minimal cuts. Under certain circumstances, the proposed one-node decomposition can produce a minimal cut for G in 0(n² ) machine operations. It is also shown that, under certain conditions, one-node cuts produce no decomposition. An alternative procedure is also introduced to overcome this situation. It is shown that this alternative procedure has the computational complexity of 0(n³).