✦ LIBER ✦

A shortest path algorithm for grid graphs

✍ Scribed by F. O. Hadlock

Publisher: John Wiley and Sons
Year: 1977
Tongue: English
Weight: 547 KB
Volume: 7
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230070404

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Faster Shortest-Path Algorithms for Plan

Faster Shortest-Path Algorithms for Planar Graphs

✍ Monika R Henzinger; Philip Klein; Satish Rao; Sairam Subramanian 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 445 KB

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we gi

An Optimal Shortest Path Parallel Algori

An Optimal Shortest Path Parallel Algorithm for Permutation Graphs

✍ O.H. Ibarra; Q. Zheng 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 512 KB

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in \(O(\log n)\) time using \(O(n / \log n)\) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be f

Termination Detection for Parallel Short

Termination Detection for Parallel Shortest Path Algorithms

✍ Michelle R Hribar; Valerie E Taylor; David E Boyce 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 322 KB

Shortest path computation is required by a large number of applications such as VLSI, transportation, and communication networks. These applications, which are often very complex and have sparse networks, generally use parallel labeling shortest path algorithms. Such algorithms, when implemented on

A dual algorithm for the constrained sho

A dual algorithm for the constrained shortest path problem

✍ Gabriel Y. Handler; Israel Zang 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 878 KB

A Randomized Parallel Algorithm for Sing

A Randomized Parallel Algorithm for Single-Source Shortest Paths

✍ Philip N Klein; Sairam Subramanian 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 179 KB

We give a randomized parallel algorithm for computing single-source shortest paths in weighted digraphs. We show that the exact shortest-path problem can be efficiently reduced to solving a series of approximate shortest-path subproblems. Our algorithm for the approximate shortest-path problem is ba

A dual simplex algorithm for finding all

A dual simplex algorithm for finding all shortest paths

✍ M. Florian; S. Nguyen; S. Pallottino 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 605 KB