Partitioning techniques for reducing computational effort of routing in large networks
M.E. Woodward, M.M.M. Al-Fawaz · IEE Proceedings - Communications · 2004
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 source–destination 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.