Physics Seminar

Finding the routes that optimize the collective transport of many interacting particles on a complex network is an important problem with many applications. Unfortunately, its solution is known to be NP-hard, meaning that its general solution requires calculations whose number grows faster than any polynomial of the number of network nodes N. Despite this fact, we have recently discovered a heuristic algorithm that works with only polynomial number of calculations which finds routes that, at least, scale optimally with network size. The algorithm, and variants of it that my group has used for different applications, minimizes the maximum node betweenness on the network thereby balancing the traffic so as to achieve the maximum network throughput without jamming. Results will be presented that show the usefulness of the optimal routes for transport on networks of different topologies and compare them to those obtained with other algorithms. The specific application of a variant of our algorithm to obtain the optimal routes for packet transport on wireless communication networks will be discussed.