Fast Exact MultiConstraint Shortest Path Algorithms

• Author(s) / Creator(s)

  • Harms, Janelle
  • Li, Yuxi
  • Holte, Robert

• Technical report TR06-22. QoS routing has been shown to be NP-hard. A recent study of its hardness shows that the ``worst-case'' may not occur in practice [13]. This suggests that there may exist fast exact algorithms for the multi-constraint shortest path (MCSP) problem, an instance of QoS routing. Search techniques such as A* and IDA* may solve hard problems exactly in polynomial time. In [14], we deploy the idea of iterative deepening search to design IDA_MCSP, and show its efficiency by extensive empirical study. In this paper, we show that for infeasible cases, IDAMCSP may not be as efficient as APrune. This motivates us to design an algorithm that is efficient in both feasible and infeasible cases. We design an exact MCSP algorithm AMCSP, which introduces the state notion and dominance relationship between states. Furthermore, we design an exact MCSP algorithm FringeMCSP. It can be regarded as an integration of IDA_MCSP and AMCSP. Extensive empirical study shows that FringeMCSP has good performance in both feasible and infeasible cases; while IDA*MCSP still shows its superiority among the proposed MCSP algorithms in feasible cases. | TRID-ID TR06-22

• Date created

  2006

• Subjects / Keywords

  • Qos routing
  • Multiconstraint Shortest Path algorithms

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3057CV2Z

• License

  Attribution 3.0 International