Partitioning techniques for reducing computational effort of routing in large networks

A new scheme is presented for partitioning a network having a specific number of nodes and degree of connectivity such that the number of operations required to find a constrained path between a source node and destination node, averaged over all sourcedestination pairs, is minimised. The scheme can speed up the routing function, possibly by orders of magnitude under favourable conditions, at the cost of a sub-optimal solution.