Abstract: | 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 (Zi, =), i= 1…, n - 1 are called one-node cuts if 1 ? Zi,. n q Zi, Z1-? {1}, Zi ? Zi+1 and Zi and Zi+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(n2 ) 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(n3). |