Fast Exact MultiConstraint Shortest Path Algorithms
Loading...
Date
Author(s)
Citation for Previous Publication
Link to Related Item
Abstract
Description
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, IDA*_MCSP may not be as efficient as A*Prune. This motivates us to design an algorithm that is efficient in both feasible and infeasible cases. We design an exact MCSP algorithm A*_MCSP, 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 A*_MCSP. 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
Item Type
http://purl.org/coar/resource_type/c_93fc
Alternative
Other License Text / Link
Subject/Keywords
Language
en