## Abstract

In this paper, we investigate the problem of finding the Delay Constrained Least Cost path (DCLC) in a network, which is NT-complete and has been extensively studied. Many proposed algorithms tackle this problem by transforming it into the shortest path selection problem or the k-shortest paths selection problem, which are P-complete, with an integrated weight function that maps the delay and cost each link into a single weight. However, they suffer from either high computational complexity or low success ratio in finding the optimal paths (the least cost path satisfying a given delay constraint). Based on the Extended Bellman-Ford (EB) algorithm, we propose a high performance algorithm, Dual Extended Bellman-Ford (DEB) algorithm, which achieves a high success ratio in finding the least cost path subject to a delay constraint with low computational complexity. Extensive simulations show that DEB outperforms its contender on all the worst-case computational complexity, average cost of the solutions, and the success ratio in finding the delay constrained least cost path.

Original language | English (US) |
---|---|

Pages | 3711-3715 |

Number of pages | 5 |

State | Published - Dec 1 2003 |

Event | IEEE Global Telecommunications Conference GLOBECOM'03 - San Francisco, CA, United States Duration: Dec 1 2003 → Dec 5 2003 |

### Other

Other | IEEE Global Telecommunications Conference GLOBECOM'03 |
---|---|

Country/Territory | United States |

City | San Francisco, CA |

Period | 12/1/03 → 12/5/03 |

## All Science Journal Classification (ASJC) codes

- Electrical and Electronic Engineering
- Global and Planetary Change

## Keywords

- Delay Constrained Least Cost Path
- Extended Bellman-Ford algorithm
- LAgrange Relaxation based Aggregated Cost (LARAC)