Shortest node-disjoint paths on random graphs

DOI10.1088/1742-5468/2014/07/P07009zbMATH Open1456.05143arXiv1401.8096OpenAlexW3101176358MaRDI QIDQ3301996FDOQ3301996

Authors:

Publication date: 11 August 2020

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• 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
• Successive shortest paths in complete graphs with random edge weights

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)