Dartmouth College Computer Science Technical Report series CS home TR home TR search TR listserv By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Quickest Paths: Faster Algorithms and Dynamization
Dimitrios Kagaris, Grammati E. Pantziou, Spyros Tragoudas, Christos D. Zaroliagis
Dartmouth PCS-TR94-204

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.

PDF (1200KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
Dimitrios Kagaris, Grammati E. Pantziou, Spyros Tragoudas, and Christos D. Zaroliagis, "Quickest Paths: Faster Algorithms and Dynamization." Dartmouth Computer Science Technical Report PCS-TR94-204, 1994.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.