A new article on arXiv analyses how hard it is to find short paths on graphs where resources (links between nodes) are scarce. This is an interesting and highly applicable piece of work – especially for those of us who use the internet and are used to slow download times!
The abstract is:
Optimal paths connecting randomly selected network nodes and fixed routers are studied analytically in the presence of non-linear overlap cost that penalizes congestion. Routing becomes increasingly more difficult as the number of selected nodes increases and exhibits ergodicity breaking in the case of multiple routers. A distributed linearly-scalable routing algorithm is devised. The ground state of such systems reveals non-monotonic complex behaviors in both average path-length and algorithmic convergence, depending on the network topology, and densities of communicating nodes and routers.
The paper can be downloaded from arxiv at: http://arxiv.org/abs/1202.0213