de Bacco, C., Franz, S., Saad, D. and Yeung, C.H. (2014). Shortest node-disjoint paths on random graphs. Journal of Statistical Mechanics, 2014 (7),
Abstract
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.
Publication DOI: | https://doi.org/10.1088/1742-5468/2014/07/P07009 |
---|---|
Divisions: | College of Engineering & Physical Sciences > Systems analytics research institute (SARI) |
Additional Information: | © 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). |
Uncontrolled Keywords: | cavity and replica method,message-passing algorithms,optimization over networks,Statistics and Probability,Statistical and Nonlinear Physics,Statistics, Probability and Uncertainty |
Publication ISSN: | 1742-5468 |
Last Modified: | 05 Aug 2024 14:35 |
Date Deposited: | 01 Jul 2015 11:30 |
Full Text Link: |
http://iopscien ... /2014/7/P07009/ |
Related URLs: |
http://www.scop ... tnerID=8YFLogxK
(Scopus URL) |
PURE Output Type: | Article |
Published Date: | 2014-07 |
Published Online Date: | 2014-07-11 |
Authors: |
de Bacco, C.
Franz, S. Saad, D. ( ![]() Yeung, C.H. |