On the Dynamic Behavior of the Min-Cut in Random Geometric Graphs

We study the minimum cut between one source and one terminal in a dynamically changing random wireless ad hoc network that is modeled as a random geometric graph. The nature of ad hoc networks is accounted for by letting nodes join and leave. Given the values of all cuts that can be formed in the original network and assuming information about the nodes that join or leave, expressions for the expected value and variance of any particular cut that may arise are derived. However, it is not possible to obtain a closed form expression for the minimum expected cut value in our framework. Nevertheless, we give a simple and reasonable upper bound for the minimum expected cut value which is also extendable to multicast transmissions.