ERA

Download the full-sized PDF of Fast Exact MultiConstraint Shortest Path AlgorithmsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3057CV2Z

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Fast Exact MultiConstraint Shortest Path Algorithms Open Access

Descriptions

Author or creator
Li, Yuxi
Harms, Janelle
Holte, Robert
Additional contributors
Subject/Keyword
Qos routing
Multiconstraint Shortest Path algorithms
Type of item
Computing Science Technical Report
Computing science technical report ID
TR06-22
Language
English
Place
Time
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.
Date created
2006
DOI
doi:10.7939/R3057CV2Z
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-24T22:34:58.936+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1537059
Last modified: 2015:10:12 17:31:36-06:00
Filename: TR06-22.pdf
Original checksum: f75643ffe1d159eccd5a652542e10089
Well formed: true
Valid: true
Page count: 12
Activity of users you follow
User Activity Date