The Edge-Disjoint Path Problem on Random Graphs by Message-Passing.

ABSTRACT: We present a message-passing algorithm to solve a series of edge-disjoint path problems on graphs based on the zero-temperature cavity equations. Edge-disjoint paths problems are important in the general context of routing, that can be defined by incorporating under a unique framework both traffic optimization and total path length minimization. The computation of the cavity equations can be performed efficiently by exploiting a mapping of a generalized edge-disjoint path problem on a star graph onto a weighted maximum matching problem. We perform extensive numerical simulations on random graphs of various types to test the performance both in terms of path length minimization and maximization of the number of accommodated paths. In addition, we test the performance on benchmark instances

SUBMITTER: Altarelli F 

PROVIDER: S-EPMC4699204 | biostudies-literature | 2015

REPOSITORIES: biostudies-literature