Finding the widest pair of arc disjiont paths
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Disjoint paths routing catches special attention in multipath research. Shortest disjoint paths problem has been studied maturely, while the research of widest disjoint paths problem is just under development. In this paper, we presented a problem of finding the widest pair of arc-disjoint paths in a directed graph. It differs from Multipath Flows, which may be transformed into the problem of Maximum Flow and Minimum Cut. Then we propose a polynomial algorithm for it with time complexity O(mnlogn). It is not required to reassign flux at common vertices on the widest pair of paths, and this scheme can be implemented easier in real networks.

    Reference
    Related
    Cited by
Get Citation
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 02,2012
  • Revised:
  • Adopted:
  • Online: November 05,2012
  • Published:
Article QR Code