MPII94110
Quickest paths: faster algorithms and dynamization
Kargaris, Dimitrios and Pantziou, Grammati E. and Tragoudas, Spyros and Zaroliagis, Christos D.
March 1994, 15 pages.
.
Status: available  back from printing
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 sourcedestination 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 allpairs quickest path problem.
We also give the first algorithm for solving the dynamic quickest path problem.

MPII94110.pdf
 Attachement: MPII94110.dvi (73 KBytes); MPII94110.pdf (123 KBytes)
URL to this document: https://domino.mpiinf.mpg.de/internet/reports.nsf/NumberView/1994110
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 = {MaxPlanckInstitut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPII94110},
MONTH = {March},
YEAR = {1994},
ISSN = {0946011X},
}