✦ LIBER ✦

Faster Shortest-Path Algorithms for Planar Graphs

✍ Scribed by Monika R Henzinger; Philip Klein; Satish Rao; Sairam Subramanian

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 445 KB
Volume: 55
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1997.1493

No coin nor oath required. For personal study only.

✦ Synopsis

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 give an algorithm requiring O(n 4Â3 log(nL)) time, where L is the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms. ] 1997 Academic Press to Goldberg [Go1], which yields O(n 3Â2 log L) time on sparse (e.g., planar) graphs. For planar graphs, Lipton, Rose, and Tarjan [LRT] showed how to solve the problem in O(n 3Â2 ) time using planar separators. Previously no article no.

📜 SIMILAR VOLUMES

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

Dual algorithms for the shortest path tr

Dual algorithms for the shortest path tree problem

✍ Pallottino, Stefano; Scutell�, Maria Grazia 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 2 views

We consider dual approaches for the Shortest Path Tree problem. After a brief introduction to the problem, we review the most important dual algorithms which have been described in the literature for its solution and propose a new family of dual ascent algorithms. In these algorithms, ''local'' and

Fully Dynamic Algorithms for Maintaining

Fully Dynamic Algorithms for Maintaining Shortest Paths Trees

✍ Daniele Frigioni; Alberto Marchetti-Spaccamela; Umberto Nanni 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 213 KB

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal quer

A Simple Parallel Algorithm for the Sing

A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs

✍ Jesper L. Träff; Christos D. Zaroliagis 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 216 KB

We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n 2= +n 1&= ) log n) time, performing O(n 1+= log n) work for any 0<=<1Â2. The strength of

An algorithm for drawing planar graphs

✍ Bor Plestenjak 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB 👁 2 views

A simple algorithm for drawing 3-connected planar graphs is presented. It is derived from the Fruchterman and Reingold spring embedding algorithm by deleting all repulsive forces and fixing vertices of an outer face. The algorithm is implemented in the system for manipulating discrete mathematical s

Parallel Algorithm for Shortest Pairs of

Parallel Algorithm for Shortest Pairs of Edge-Disjoint Paths

✍ S. Banerjee; R.K. Ghosh; A.P.K. Reddy 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 241 KB

method a solution for MSP can be found within the same time bound. The problem of finding all pairs of shortest paths in a directed graph with nonnegative edge weights can be solved in O(log 2 n) time using n 3 /log n processors on a CREW PRAM [7]. Therefore, SSP can be solved within the same resou