✦ LIBER ✦

An efficient implementation of an algorithm for findingK shortest simple paths

✍ Scribed by Hadjiconstantinou, E.; Christofides, N.

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 263 KB
Volume: 34
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199909)34:2<88::aid-net2>3.0.co;2-1

No coin nor oath required. For personal study only.

✦ Synopsis

In this article, we present an efficient computational implementation of an algorithm for finding the K shortest simple paths connecting a pair of vertices in an undirected graph with n vertices, m arcs, and nonnegative arc lengths. A minimal number of intermediate paths is formed based on the method of Katoh, Ibaraki and Mine [Networks 12 (1982), 411-427], which has the lowest worst-case complexity of O(n 2 ) among all other existing algorithms for this problem. A theoretical description of the algorithm is presented with detailed explanations and some examples of the more complicated steps. Efficient data structures for storing and retrieving a large number of paths are given. The results of wide-ranging experimentation with a large number of randomly generated graphs of varying size and density confirm the linear dependency of computing time on K, as proven in Katoh et al., and the quadratic dependency of computing time on graph size as suggested by the worst-case computational complexity.

📜 SIMILAR VOLUMES

An Incremental Algorithm for a Generaliz

An Incremental Algorithm for a Generalization of the Shortest-Path Problem

✍ G. Ramalingam; Thomas Reps 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 363 KB

The grammar problem, a generalization of the single-source shortest-path prob-Ž Ž . Ž . . lem introduced by D. E. Knuth Inform. Process. Lett. 6 1 1977 , 1᎐5 is to compute the minimum-cost derivation of a terminal string from each nonterminal of a given context-free grammar, with the cost of a deriv

An efficient concurrent implementation o

An efficient concurrent implementation of a neural network algorithm

✍ R. Andonie; A. T. Chronopoulos; D. Grosu; H. Galmeanu 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

The focus of this study is how we can efficiently implement the neural network backpropagation algorithm on a network of computers (NOC) for concurrent execution. We assume a distributed system with heterogeneous computers and that the neural network is replicated on each computer. We propose an arc

An Efficient Implementation of a Scaling

An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm

✍ Andrew V Goldberg 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 338 KB

An Efficient Algorithm for the k-Pairwis

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

✍ Qian-Ping Gu; Shietung Peng 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 140 KB

A graph G(V, E) (|V| 2k) satisfies property A k if, given k pairs of distinct nodes (s 1 , t 1 ), ..., (s k , t k ) of V(G), there are k mutually node-disjoint paths, one connecting s i and t i for each i, 1 i k. A necessary condition for any graph to satisfy A k is that it is (2k&1)-connected. Hype

An efficient serial distributed arithmet

An efficient serial distributed arithmetic algorithm for FPGA implementation of digital up conversion

✍ T. Salim; J. Devlin; J. Whittington; M. I. Bhatti 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 334 KB

A simpleO(n2) algorithm for the all-pair

A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph

✍ Mirchandani, Prakash 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 3 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a