Shortest node-disjoint paths on random graphs

C. de Bacco, S. Franz, D. Saad, C.H. Yeung

    Research output: Contribution to journalArticlepeer-review


    A localized method to distribute paths on random graphs is devised, aimed at finding the shortest paths between given source/destination pairs while avoiding path overlaps at nodes. We propose a method based on message-passing techniques to process global information and distribute paths optimally. Statistical properties such as scaling with system size and number of paths, average path-length and the transition to the frustrated regime are analyzed. The performance of the suggested algorithm is evaluated through a comparison against a greedy algorithm.

    Original languageEnglish
    Article numberP07009
    Number of pages21
    JournalJournal of Statistical Mechanics
    Issue number7
    Early online date11 Jul 2014
    Publication statusPublished - Jul 2014

    Bibliographical note

    © 2014 IOP Publishing Ltd and SISSA Medialab srl.

    Funding: Marie Curie Training Network NETADIS (FP7, grant 290038); EU FET FP7 project STAMINA (FP7–265496); Royal Society Exchange Grant IE110151; “Laboratoire d’Excellence Physics Atom Light Matter” (LabEx PALM) overseen by the French National Research Agency (ANR) as part of the “Investissements d’Avenir” program (reference: ANR-10-LABX-0039); and Research Grants Council of Hong Kong (605010 and 604512).


    • cavity and replica method
    • message-passing algorithms
    • optimization over networks


    Dive into the research topics of 'Shortest node-disjoint paths on random graphs'. Together they form a unique fingerprint.

    Cite this