Shortest node-disjoint paths on random graphs

DOI10.1088/1742-5468/2014/07/P07009MaRDI QIDQ3301996zbMATH OpenOpenAlexFDO

Authors

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.8096

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Communication networks in operations research (90B18)

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 analysed. The performance of the suggested algorithm is evaluated through a comparison against a greedy algorithm.

Recommendations

• Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• On the construction of all shortest node-disjoint paths in star networks
• scientific article; zbMATH DE number 1003293
• Distributed algorithms for computing shortest pairs of disjoint paths

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1187149 (Why is no real title available?)
• scientific article; zbMATH DE number 1256778 (Why is no real title available?)
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• A post-optimization method for the routing and wavelength assignment problem applied to scheduled lightpath demands
• Differential evolution -- a simple and efficient heuristic for global optimization over continuous spaces
• From the physics of interacting polymers to optimizing routes on the London underground
• Graph minors. XIII: The disjoint paths problem
• Information, Physics, and Computation
• Poly-logarithmic approximation for maximum node disjoint paths with constant congestion
• Reducibility among combinatorial problems
• Routing and wavelength assignment in optical networks using bin packing based algorithms
• Statistical mechanics of complex networks
• The cavity method at zero temperature

Cited in

(9)

• Successive shortest paths in complete graphs with random edge weights
• Solving the edge‐disjoint paths problem using a two‐stage method
• Developments in the theory of randomized shortest paths with a comparison of graph node distances
• Short disjoint paths in locally connected graphs
• The cavity approach for Steiner trees packing problems
• The shortest-path problem for graphs with random arc-lengths
• Self-organization scheme for balanced routing in large-scale multi-hop networks
• Shortest edge-disjoint paths in graphs
• Minimal functional routes in directed graphs with dependent edges

This page was built for publication: Shortest node-disjoint paths on random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301996)