Shortest node-disjoint paths on random graphs

BACCO Caterina DE, Silvio FRANZ, David SAAD, Chi Ho YEUNG

Research output: Contribution to journalArticle

5 Citations (Scopus)

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. Copyright © 2014 IOP Publishing Ltd and SISSA Medialab srl.
Original languageEnglish
Article numberP07009
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2014
DOIs
Publication statusPublished - Jul 2014

Fingerprint

Disjoint Paths
Random Graphs
Path
Vertex of a graph
Path Length
Message Passing
Greedy Algorithm
greedy algorithms
Shortest path
Statistical property
Overlap
Scaling
messages
Node
Random graphs
scaling
Greedy algorithm
Destination

Citation

De Bacco, C., Franz, S., Saad, D., & Yeung, C. H. (2014). Shortest node-disjoint paths on random graphs. Journal of Statistical Mechanics: Theory and Experiment, 2014. Retrieved from http://dx.doi.org/10.1088/1742-5468/2014/07/P07009

Keywords

  • Cavity and replica method
  • Optimization over networks
  • Message-passing algorithms