Competition for shortest paths on sparse graphs

Chi Yeung, David Saad

    Research output: Contribution to journalArticlepeer-review


    Optimal paths connecting randomly selected network nodes and fixed routers are studied analytically in the presence of a nonlinear overlap cost that penalizes congestion. Routing becomes more difficult as the number of selected nodes increases and exhibits ergodicity breaking in the case of multiple routers. The ground state of such systems reveals nonmonotonic complex behaviors in average path length and algorithmic convergence, depending on the network topology, and densities of communicating nodes and routers. A distributed linearly scalable routing algorithm is also devised. © 2012 American Physical Society.
    Original languageEnglish
    Article number208701
    Number of pages5
    JournalPhysical Review Letters
    Issue number20
    Publication statusPublished - 14 May 2012

    Bibliographical note

    © APS


    Dive into the research topics of 'Competition for shortest paths on sparse graphs'. Together they form a unique fingerprint.

    Cite this