Finding Multi-Constrained Paths Using Depth-First Search

Zhenjiang Li
UCSC

Nov 15, 3pm, Engineering 2, Room 316

ABSTRACT

EDFS is an efficient and quick constrained path-selection algorithm based on linear-time graph traversal method depth-first search (DFS). Though there have been many heuristics proposed to solve MCP, only few of them address the general k-constrained path-selection problem. One unique property of EDFS is that the tighter the constraints are, the better the performance it can achieve. In particular, EDFS can achieve almost the same success ratio as an exact solution does (with exponential running time complexity), while having less running time than that of Dijkstra's algorithm when the routing constraints are very tight. This is valuable to QoS routing in dynamic environment such as wireless ad hoc networks in which network topology and link state keep changing, and real-time or multimedia applications that have stringent QoS requirements.

Back