One-to-many node-disjoint paths routing in dense gaussian networks

In this paper, an efficient constant time complexity algorithm that constructs node disjoint paths (NDP) from a single source node to the maximum number of destination nodes in dense Gaussian networks is given. Then, it is proved that this algorithm always returns a solution. Also, the lower and upper bounds of the sum of the NDP lengths are derived. Finally, via execution of the algorithm, it is shown that on the average the sum of lengths of NDP given by the algorithm is only ∼10% more than the sum of the shortest paths lengths.