Shortest node-disjoint paths on random graphs

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

doi:10.1088/1742-5468/2014/07/P07009

Shortest node-disjoint paths on random graphs

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

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	P07009
Number of pages	21
Journal	Journal of Statistical Mechanics
Volume	2014
Issue number	7
Early online date	11 Jul 2014
DOIs	https://doi.org/10.1088/1742-5468/2014/07/P07009
Publication status	Published - 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).

Keywords

cavity and replica method
message-passing algorithms
optimization over networks

Access to Document

10.1088/1742-5468/2014/07/P07009

Shortest node-disjoint paths on random graphs
© 2014 IOP Publishing Ltd and SISSA Medialab srl.
Accepted author manuscript, 458 KB

http://iopscience.iop.org/1742-5468/2014/7/P07009/

Cite this

@article{ce985aa6042e42a79da35e0a0b7109a0,

title = "Shortest node-disjoint paths on random graphs",

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.",

keywords = "cavity and replica method, message-passing algorithms, optimization over networks",

author = "{de Bacco}, C. and S. Franz and D. Saad and C.H. Yeung",

note = "{\textcopyright} 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{\textquoteright}Excellence Physics Atom Light Matter” (LabEx PALM) overseen by the French National Research Agency (ANR) as part of the “Investissements d{\textquoteright}Avenir” program (reference: ANR-10-LABX-0039); and Research Grants Council of Hong Kong (605010 and 604512).",

year = "2014",

month = jul,

doi = "10.1088/1742-5468/2014/07/P07009",

language = "English",

volume = "2014",

journal = "Journal of Statistical Mechanics",

issn = "1742-5468",

publisher = "IOP Publishing Ltd.",

number = "7",

}

TY - JOUR

T1 - Shortest node-disjoint paths on random graphs

AU - de Bacco, C.

AU - Franz, S.

AU - Saad, D.

AU - Yeung, C.H.

N1 - © 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).

PY - 2014/7

Y1 - 2014/7

N2 - 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.

AB - 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.

KW - cavity and replica method

KW - message-passing algorithms

KW - optimization over networks

UR - http://www.scopus.com/inward/record.url?scp=84905188438&partnerID=8YFLogxK

U2 - 10.1088/1742-5468/2014/07/P07009

DO - 10.1088/1742-5468/2014/07/P07009

M3 - Article

AN - SCOPUS:84905188438

SN - 1742-5468

VL - 2014

JO - Journal of Statistical Mechanics

JF - Journal of Statistical Mechanics

IS - 7

M1 - P07009

ER -

Shortest node-disjoint paths on random graphs

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this