# MPI-I-94-110

## Quickest paths: faster algorithms and dynamization

### Kargaris, Dimitrios and Pantziou, Grammati E. and Tragoudas, Spyros and Zaroliagis, Christos D.

**MPI-I-94-110**. March** **1994, 15 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

Given a network $N=(V,E,{c},{l})$, where

$G=(V,E)$, $|V|=n$ and $|E|=m$,

is a directed graph, ${c}(e) > 0$ is the capacity

and ${l}(e) \ge 0$ is the lead time (or delay) for each edge $e\in E$,

the quickest path problem is to find a path for a

given source--destination pair such that the total lead time plus the

inverse of the minimum edge capacity of the path

is minimal. The problem has applications to fast data

transmissions in communication networks. The best previous algorithm for the

single pair quickest path problem runs in time $O(r m+r n \log n)$,

where $r$ is the number of distinct capacities of $N$.

In this paper,

we present algorithms for general, sparse and planar

networks that have significantly lower running times.

For general networks, we show that the time complexity can be

reduced to $O(r^{\ast} m+r^{\ast} n \log n)$,

where $r^{\ast}$ is at most the number of capacities greater than the

capacity of the shortest (with respect to lead time) path in $N$.

For sparse networks, we present an algorithm with time complexity

$O(n \log n + r^{\ast} n + r^{\ast} \tilde{\gamma} \log \tilde{\gamma})$,

where $\tilde{\gamma}$ is a topological measure of $N$.

Since for sparse networks $\tilde{\gamma}$ ranges from $1$

up to $\Theta(n)$,

this constitutes an improvement over the previously known bound of

$O(r n \log n)$ in all cases that $\tilde{\gamma}=o(n)$.

For planar networks, the complexity becomes $O(n \log n +

n\log^3 \tilde{\gamma}+ r^{\ast} \tilde{\gamma})$.

Similar improvements are obtained

for the all--pairs quickest path problem.

We also give the first algorithm for solving the dynamic quickest path problem.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-94-110.pdf | 73 KBytes; 123 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-110

**BibTeX**
`@TECHREPORT{``KargarisPantziouTragoudasZaroliagis94``,`

` AUTHOR = {Kargaris, Dimitrios and Pantziou, Grammati E. and Tragoudas, Spyros and Zaroliagis, Christos D.},`

` TITLE = {Quickest paths: faster algorithms and dynamization},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-94-110},`

` MONTH = {March},`

` YEAR = {1994},`

` ISSN = {0946-011X},`

`}`