BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR94-204
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Quickest Paths: Faster Algorithms and Dynamization
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Kagaris, Dimitrios
AUTHOR:: Pantziou, Grammati E.
AUTHOR:: Tragoudas, Spyros
AUTHOR:: Zaroliagis, Christos D.
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1994
ABSTRACT::
	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$ \cite{ROS}.  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.
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR94-204.pdf
END::